python - 一般酒吧和星星

Question

我有以下 "bars and stars"算法，用 Python 实现，它打印出总和的所有分解到 3 个箱子中，总和从 0 到 5。 我想概括我的代码，以便它适用于 N 个 bin(其中 N 小于最大总和，即此处为 5)。 模式是，如果您有 3 个箱子，则需要 2 个嵌套循环，如果您有 N 个箱子，则需要 N-1 个嵌套循环。

有人能想出一种通用的编写方法，可能不使用循环吗？

# bars and stars algorithm
N=5
for n in range(0,N):
    x=[1]*n
    for i in range(0,(len(x)+1)):
        for j in range(i,(len(x)+1)):
            print sum(x[0:i]), sum(x[i:j]), sum(x[j:len(x)])

Answer 1

如果这不仅仅是一个学习练习，那么您就没有必要使用自己的算法来生成分区:Python 的标准库已经拥有您需要的大部分内容，形式为 itertools.combinations功能。

来自 Wikipedia page 上的定理 2你链接到，有 n+k-1 choose k-1 方法将 n 项分成 k bins，以及证明定理给出了组合和分区之间的明确对应关系。所以我们所需要的只是 (1) 一种生成这些组合的方法，以及 (2) 将每个组合转换为相应分区的代码。 itertools.combinations 函数已经提供了第一种成分。第二，每个组合给出分隔线的位置；连续分隔符位置之间的差异(减一)给出了分区大小。这是代码:

import itertools

def partitions(n, k):
    for c in itertools.combinations(range(n+k-1), k-1):
        yield [b-a-1 for a, b in zip((-1,)+c, c+(n+k-1,))]

# Example usage
for p in partitions(5, 3):
    print(p)

这是运行上述代码的输出。

[0, 0, 5]
[0, 1, 4]
[0, 2, 3]
[0, 3, 2]
[0, 4, 1]
[0, 5, 0]
[1, 0, 4]
[1, 1, 3]
[1, 2, 2]
[1, 3, 1]
[1, 4, 0]
[2, 0, 3]
[2, 1, 2]
[2, 2, 1]
[2, 3, 0]
[3, 0, 2]
[3, 1, 1]
[3, 2, 0]
[4, 0, 1]
[4, 1, 0]
[5, 0, 0]