python - 一般酒吧和星星

我有以下用Python实现的"bars and stars"算法，该算法将总和的所有分解输出到3个bin中，总和从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)])

最佳答案

一次迈出一步。

首先，删除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时给您带来麻烦。