有一个巧妙的技巧可以解决这个问题。想象一下我们采取了n球和m− 1 个盒子并将它们排成一排n + m− 1(盒子与球混在一起)。然后将每个球放入其右侧的盒子中,并在右侧添加第 m 个盒子,用于放置剩余的球。
这会产生一个排列n球进m boxes.
It is easy to see that there are the same number of arrangements of n balls in sequence with m − 1 boxes (the first picture) as there are arrangements of n balls in m boxes. (To go one way, put each ball in the box to its right; to go the other way, each box empties the balls into the positions to its left.) Each arrangement in the first picture is determined by the positions where we put the boxes. There are m − 1 boxes and n + m − 1 positions, so there are n + m − 1Cm − 1 ways to do that.
所以你只需要一个普通的组合算法(看到这个问题)生成盒子的可能位置,然后取连续位置之间的差值(小于 1)来计算每个盒子中球的数量。
在Python中这会非常简单,因为有一个组合标准库中的算法:
from itertools import combinations
def balls_in_boxes(n, m):
"""Generate combinations of n balls in m boxes.
>>> list(balls_in_boxes(4, 2))
[(0, 4), (1, 3), (2, 2), (3, 1), (4, 0)]
>>> list(balls_in_boxes(3, 3))
[(0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0), (3, 0, 0)]
"""
for c in combinations(range(n + m - 1), m - 1):
yield tuple(b - a - 1 for a, b in zip((-1,) + c, c + (n + m - 1,)))