生成“箱子中的球”结果的算法，并限制箱子大小？

Question

假设我们有N个球和M个箱子要放进去。这方面的结果数量可以使用“星条旗”方法Integer Equations - Stars and Bars找到。我们还可以使用itertools包计算所有实际结果，并使用sympy.utilities.iterables.multiset_permutations获得唯一的结果

但是，如果我们将bin大小限制为[0，N]上的某个任意数字，您如何有效地计算所有可能的结果？有没有比计算所有结果而不计算仓位大小，然后消除无效结果更好的方法

对于N=2和M=3，结果为{200, 110, 020, 011, 101, 002}

例如，当N=3和M=3时，结果是{300, 210, 120, 021, 012, 030, 201, 102, 003, 111}。但是，如果我们需要一些数组b=[3,3,0]来指定最大bin大小，这样唯一有效的结果就是{300, 210, 120, 030}，该怎么办呢

Answer 1

您可以使用递归方法将0到最大球放置在第一个箱子上，并与剩余球一起递归放置在其余箱子上：

def ballPlacing(N,B):
    if N <= 0: return int(N==0)
    if len(B) == 1:
        return int(N<=B[0])
    total = 0
    for c in range(min(N,B[0])+1):
        total += ballPlacing(N-c,B[1:])
    return total

print(ballPlacing(3,[3,3,3])) # 10
print(ballPlacing(3,[3,3,0])) # 4