Python:递归创建带有条件的整数列表的列表

Question

我想创建 n 个项目的所有可能分布。这指的是众所周知的鸽巢原理。

以下值是 Microsoft Excel 的结果:

get_distributions(list, number_of_items_to_distribute)
get_distributions([], 1) = [[1]]
get_distributions([], 2) = [[1, 1], [2]]
get_distributions([], 3) = [[1, 1, 1], [1, 2], [2, 1], [3]]
get_distributions([], 4) = [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]

我已经有了一些代码，但删除临时列表时存在一些问题。

all_distributions = []

def get_distributions(distribution, items):

    print('call with distribution = ' + str(distribution) + ', items = ' + str(items))
    print('---------------')

    # base case
    if items == 0:
        all_distributions.append(distribution)
        print('end: ' + str(distribution))
        distribution.clear()
        return []

    # recursion
    else:
        for i in range(1, items + 1):
            distribution.append(i)
            get_distributions(distribution, items - i)

这样我就可以在“end:”之后打印出良好的结果，但是缺少一些值，例如 [1, 2](使用 n = 3 调用)。除此之外，这些值不会附加到我的 all_distributions 中。

我对我尝试解决这个问题的方式感兴趣。这是一个好方法还是我完全错了？

Answer 1

代码的主要问题是列表 all_distributions 最终包含对同一输入列表 distribution 的许多引用。当您调用 all_distributions.append(distribution) 时，列表 distribution 不会复制到列表 all_distributions 中，而只是对该列表的引用附加。您可以通过显式插入副本来解决此问题:all_distributions.append(list(distribution))

对代码的最小修复是插入副本，删除基本情况中的 distribution.clear() ，并在递归调用后添加 distribution.pop() :

all_distributions = []

def get_distributions(distribution, items):
    if items == 0:
        all_distributions.append(list(distribution))
    else:
        for i in range(1, items + 1):
            distribution.append(i)
            get_distributions(distribution, items - i)
            distribution.pop()

get_distributions([], 3)
print(all_distributions)

输出:[[1, 1, 1], [1, 2], [2, 1], [3]]

<小时/>

更好的方法是避免使用 distribution.append，而是在列表上使用加号运算符，如下所示:

def get_distributions(distribution, items):
    if items == 0:
        all_distributions.append(distribution)
    else:
        for i in range(1, items + 1):
            d = distribution + [i]
            get_distributions(d, items - i)

列表上的加号运算符通过连接两个给定列表来创建一个新列表。在本例中，我们在 distribution 右侧连接单个元素 i 以获得包含 distribution 中元素的新副本，然后是我。

<小时/>

另一个改进是避免使用全局变量all_distributions，而是返回分布列表:

def get_distributions(distribution, items):
    if items == 0:
        return [distribution]
    else:
        all_distributions = []
        for i in range(1, items + 1):
            d = distribution + [i]
            all_distributions += get_distributions(d, items - i)
        return all_distributions

print(get_distributions([], 4))

输出:[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [ 2, 2], [3, 1], [4]]