一般酒吧和星星 [英] General bars and stars

问题描述

我有以下酒吧和星星算法，在Python中，打印出的款项全部分解成3箱，用于款项会从0到5执行。 我想推广我的code所以它的工作原理与N个频点（其中超过最大总和即5其中N以下）。 该模式是，如果你有3箱则需要2个嵌套循环，如果你有N个频点需要N-1嵌套循环。

有人能想到写这样一个通用的方法，可能不使用循环？

 ＃酒吧和星级算法
N = 5
对于n的范围（0，N）：
    X = [1] * n个
    因为我在范围（0，（LEN（X）+1））：
        对于j的范围（我，（LEN（X）+1））：
            打印总和（X [0：I]），和（X [I：J]），总和（X [J：LEN（X）]）
 

解决方案

把它一步一步的时间。

首先，删除和（）通话。我们不需要他们：

  N = 5
对于n的范围（0，N）：
    X = [1] * n个
    对于i在范围（0，第（n + 1））：＃的len（x）的==Ñ
        对于j的范围（ⅰ，第（n + 1））：
            打印I，J  -  I，N  -  J
 

注意 X 是一个未使用的变量：

  N = 5
对于n的范围（0，N）：
    对于i在范围（0，第（n + 1））：
        对于j的范围（ⅰ，第（n + 1））：
            打印I，J  -  I，N  -  J
 

时间一概而论。上面的算法是正确的 N 星和3个酒吧，所以我们只需要概括吧。

如此这般。为碱的情况下，我们有任一零杆或零分，这两者都是微不足道的。对于递归的情况下，通过运行在最左边栏和递归在每种情况下的所有可能的位置：

 从__future__进口print_function

高清bars_and_stars（酒吧= 3，星星= 5，_ preFIX =''）：
    如果明星== 0：
        打印（_ preFIX +'，'。加入（0*（棒+ 1）））
        返回
    如果酒吧== 0：
        打印（_ preFIX + STR（星星））
        返回
    因为我在范围内（星+ 1）：
        bars_and_stars（酒吧-1，星星，我，'{} {}，.format（_ preFIX，I））
 

有关加分，我们可以修改范围（）到的xrange（），但这只会给你麻烦，当你口到Python 3。

I've got a the following "bars and stars" algorithm, implemented in Python, which prints out all decomposition of a sum into 3 bins, for sums going from 0 to 5. I'd like to generalise my code so it works with N bins (where N less than the max sum i.e 5 here). The pattern is if you have 3 bins you need 2 nested loops, if you have N bins you need N-1 nested loops.

Can someone think of a generic way of writing this, possibly not using loops?

# 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)])

解决方案

Take it one step at a time.

First, remove the sum() calls. We don't need them:

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

Notice that x is an unused variable:

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

Time to generalize. The above algorithm is correct for N stars and three bars, so we just need to generalize the bars.

Do this recursively. For the base case, we have either zero bars or zero stars, which are both trivial. For the recursive case, run through all the possible positions of the leftmost bar and recurse in each case:

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))

For bonus points, we could change range() to xrange(), but that will just give you trouble when you port to Python 3.

这篇关于一般酒吧和星星的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！