一般酒吧和星星

Question

我有一个以下的"条形和星形"算法,用Python实现,它将所有分解打印成3个分箱,总和从0到5.我想概括我的代码,所以它适用于N个箱(其中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函数的形式提供了你需要的大部分内容.

从您链接到的维基百科页面上的定理2 中,有将n+k-1 choose k-1方法划分n为k区间的方法,该定理的证明给出了组合和分区之间的明确对应关系.所以我们需要的是(1)生成这些组合的方法,以及(2)将每个组合转换为相应分区的代码.该itertools.combinations功能已经提供了第一个成分.对于第二种,每种组合给出分隔物的位置; 连续分隔符位置(减1)之间的差异给出了分区大小.这是代码:

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]

Answer 2

一步一步地进行。

首先，删除sum()呼叫。我们不需要它们：

N=5
for n in range(0,N):
    x=[1]*n
    for i in range(0,(n+1)):  # len(x) == n
        for j in range(i,(n+1)):
            print i, j - i, n - j

请注意，这x是一个未使用的变量：

N=5
for n in range(0,N):
    for i in range(0,(n+1)):
        for j in range(i,(n+1)):
            print i, j - i, n - j

是时候概括一下了。上面的算法对于N星星和三个条形是正确的，所以我们只需要概括这些条形。

递归地执行此操作。对于基本情况，我们要么有零条，要么有零颗星，这都是微不足道的。对于递归情况，遍历最左边条形的所有可能位置并在每种情况下递归：

from __future__ import print_function

def bars_and_stars(bars=3, stars=5, _prefix=''):
    if stars == 0:
        print(_prefix + ', '.join('0'*(bars+1)))
        return
    if bars == 0:
        print(_prefix + str(stars))
        return
    for i in range(stars+1):
        bars_and_stars(bars-1, stars-i, '{}{}, '.format(_prefix, i))

为了奖励积分，我们可以更改range()为xrange()，但这只会在您移植到 Python 3 时给您带来麻烦。