我想枚举A框中N个球的所有可能组合。
示例：我有8个球要处理3 个盒子：
box_1 box_2 box_3
case-1 8 0 0
case-2 0 8 0
case-3 0 0 8
case-4 7 1 0
case-5 7 0 1
case-6 6 2 0
...
我的第一个问题是我需要A循环来执行此操作，但我希望A和N成为用户的输入。那么如何在不编写用户可能需要的所有可能数量的循环的情况下呢？
a和N的值在 2 到 ~800 之间，因此对计算时间的要求很高。如何优化该算法？
如果您使用 python 语言回答我，我将不胜感激。感谢所有贡献！
从 python 2.6 开始，这工作得很好，（也可以使用2.5 友好的实现itertools.permutations）：
>>> import itertools
>>> boxes = 3
>>> balls = 8
>>> rng = list(range(balls + 1)) * boxes
>>> set(i for i in itertools.permutations(rng, boxes) if sum(i) == balls)
{(0, 1, 7), (3, 1, 4), (0, 4, 4), (1, 0, 7), (4, 0, 4), (3, 0, 5), (1, 2, 5), (1, 7, 0), (0, 8, 0), (1, 4, 3), (6, 0, 2), (4, 3, 1), (3, 3, 2), (0, 5, 3), (5, 3, 0), (5, 1, 2), (2, 4, 2), (4, 4, 0), (3, 2, 3), (7, 1, 0), (5, 2, 1), (0, 6, 2), (6, 1, 1), (2, 2, 4), (1, 1, 6), (0, 2, 6), (7, 0, 1), (2, 1, 5), (0, 0, 8), (2, 0, 6), (2, 6, 0), (5, 0, 3), (2, 5, 1), (1, 6, 1), (8, 0, 0), (4, 1, 3), (6, 2, 0), (3, 5, 0), (0, 3, 5), (4, 2, 2), (1, 3, 4), (0, 7, 1), (1, 5, 2), (2, 3, 3), (3, 4, 1)}
伪代码：
Enumerate(Balls, Boxes)
if Boxes<=0
Error
elseif Boxes=1
Box[1] = Balls
PrintBoxes
else
forall b in 0..Balls
Box[Boxes] = b
Enumerate(Balls-b, Boxes-1)
endfor
endif
end
解释
从第一个盒子开始，如果没有盒子，抱怨并退出。如果它是最后一个要填充的盒子，则丢弃所有剩余的球并显示结果。如果有更多的盒子，首先添加0个球，然后对其他盒子重复该过程。然后添加1，球2个球，直到没有球离开。
为了证明该算法有效，我举了一个真实值的例子，3 个球和 2 个盒子。
我们有一个称为 Box 的盒子数组，每个盒子可以容纳任意数量的球（值）。PrintBoxes 打印框的当前值。
Box = (0,0)
Enumerate(3, 2)
b=0
Box = (0,0)
Enumerate(3,1)
Box = (3,0)
Print!
b=1
Box = (0,1)
Enumerate(2,1)
Box = (2,1)
Print!
b=2
Box = (0,2)
Enumerate(1,1)
Box = (1,2)
Print!
b=3
Box = (0,3)
Enumerate(0,1)
Box = (0,3)
Print!
Output:
(3,0)
(2,1)
(1,2)
(0,3)
Which are all the combinations.
另一个有 3 个盒子和 3 个球的例子：
Box = (0,0,0)
Enumerate(3, 3)
b=0
Box = (0,0,0)
Enumerate(3,2)
b=0
Box = (0,0,0)
Enumerate(3,1)
Box = (3,0,0)
b=1
Box = (0,1,0)
Enumerate(2,1)
Box = (2,1,0)
b=2
Box = (0,2,0)
Enumerate(1,1)
Box = (1,2,0)
b=3
Box = (0,3,0)
Enumerate(0,1)
Box = (0,3,0)
b=1
Box = (0,0,1)
Enumerate(2,2)
b=0
Box = (0,0,1)
Enumerate(2,1)
Box = (2,0,1)
b=1
Box = (0,1,1)
Enumerate(1,1)
Box = (1,1,1)
b=2
Box = (0,2,1)
Enumerate(0,1)
Box = (0,2,1)
b=2
Box = (0,0,2)
Enumerate(1,2)
b=0
Box = (0,0,2)
Enumerate(1,1)
Box = (1,0,2)
b=1
Box = (0,1,2)
Enumerate(0,1)
Box = (0,1,2)
b=3
Box = (0,0,3)
Enumerate(0,2)
b=0
Box = (0,0,3)
Enumerate(0,1)
Box = (0,0,3)
Output
(3,0,0)
(2,1,0)
(1,2,0)
(0,3,0)
(2,0,1)
(1,1,1)
(0,2,1)
(1,0,2)
(0,1,2)
(0,0,3)
请参阅3.1 中的itertools.combinations_with_replacement以获取用 python 编写的示例。此外，在组合学中，将替换组合问题转换为通常的组合不替换问题是很常见的，这已经内置在 2.6 itertools 中。这具有不生成丢弃元组的优点，例如基于乘积或排列的解决方案。这是一个使用标准 (n, r) 术语的示例，在您的示例中为 (A, N)。
import itertools, operator
def combinations_with_replacement_counts(n, r):
size = n + r - 1
for indices in itertools.combinations(range(size), n-1):
starts = [0] + [index+1 for index in indices]
stops = indices + (size,)
yield tuple(map(operator.sub, stops, starts))
>>> list(combinations_with_replacement_counts(3, 8))
[(0, 0, 8), (0, 1, 7), (0, 2, 6), (0, 3, 5), (0, 4, 4), (0, 5, 3), (0, 6, 2), (0, 7, 1), (0, 8, 0), (1, 0, 7), (1, 1, 6), (1, 2, 5), (1, 3, 4), (1, 4, 3), (1, 5, 2), (1, 6, 1), (1, 7, 0), (2, 0, 6), (2, 1, 5), (2, 2, 4), (2, 3, 3), (2, 4, 2), (2, 5, 1), (2, 6, 0), (3, 0, 5), (3, 1, 4), (3, 2, 3), (3, 3, 2), (3, 4, 1), (3, 5, 0), (4, 0, 4), (4, 1, 3), (4, 2, 2), (4, 3, 1), (4, 4, 0), (5, 0, 3), (5, 1, 2), (5, 2, 1), (5, 3, 0), (6, 0, 2), (6, 1, 1), (6, 2, 0), (7, 0, 1), (7, 1, 0), (8, 0, 0)]
您可以定义一个递归生成器，它为您希望嵌套的每个“for循环”创建一个子生成器，如下所示：
def ballsAndBoxes(balls, boxes, boxIndex=0, sumThusFar=0):
if boxIndex < (boxes - 1):
for counter in xrange(balls + 1 - sumThusFar):
for rest in ballsAndBoxes(balls, boxes,
boxIndex + 1,
sumThusFar + counter):
yield (counter,) + rest
else:
yield (balls - sumThusFar,)
当你在顶层调用它时，它只需要一个 'balls' 和 'boxes' 参数，其他参数作为默认值存在，以便递归调用可以传递不同的东西。它将产生作为您的值的整数元组（长度为“框”）。
要获得您在本文顶部指定的确切格式，您可以这样称呼它：
BALLS = 8
BOXES = 3
print '\t',
for box in xrange(1, BOXES + 1):
print '\tbox_%d' % (box,),
print
for position, value in enumerate(ballsAndBoxes(BALLS, BOXES)):
print 'case-%d\t\t%s' % (position + 1,
"\t".join((str(v) for v in value)))
使用 python 生成器是个好主意，就像上面所做的那样，但这里是更直接（不确定效率）的版本：
def balls_in_baskets(balls=1, baskets=1):
if baskets == 1:
yield [balls]
elif balls == 0:
yield [0]*baskets
else:
for i in xrange(balls+1):
for j in balls_in_baskets(balls-i, 1):
for k in balls_in_baskets(i, baskets-1):
yield j+k
for i in balls_in_baskets(8,3):
print i
如果您只是想知道可能性的数量，而不是列出它们，那么以下公式将起作用：
可能性 = (N+A-1) CN = (N+A-1)!/(N!x(A-1)!)
其中 aCb（a 选择 b）是从一组尺寸 a 中选择尺寸 b 组合的方式的数量。
！表示阶乘，即 5!=5*4*3*2*1, n!=n*(n-1)*(n-2)*...*3*2*1。对不起，如果我教你如何吸鸡蛋。
在蟒蛇中：
from math import factorial as f
balls=N
boxes=A
def p(balls,boxes):
return f(balls+boxes-1)/f(balls)/f(boxes-1)
p(3,2)
4
p(3,3)
10
这与 Gamecat 的示例一致。
为了解释这个公式为什么有效，让我们看一下五个球和三个盒子。用星号表示球。我们要放置 3-1=2 分割线将球分成 3 个隔间。
例如，我们可以有
* | * | * * * (1,1,3)
* * | * * * | (2,3,0)
* * * * * | | (5,0,0)
7 个符号可以以 7!=5040 种可能的方式排序。由于所有的球都是一样的，我们不担心球的顺序，所以我们除以 5！。同样，我们不担心分割线的顺序，所以我们除以 2！。这给了我们 7C5=7!/(5!*2!)=21 种可能性。
维基百科关于组合的文章有一个“重复组合的数量”部分，这是以更美味的方式重新表述的计数组合问题（甜甜圈和水果片而不是球）。
如果要列出组合，请注意数字增长的速度。20个球和9个盒子，就有超过300万种可能性！
编辑：我之前的回答将此问题与整数分区进行了比较，以显示可能性数量增长的速度。我的新答案与原始问题更相关。
如果您想使用 Gamecat 自己的函数答案，也可以使用http://probstat.sourceforge.net/，它非常快（用 c 编写）
或 python 2.6 中的 itertools
def iterate_assignments(N, K):
buckets = [0] * K
buckets[0] = K
while True:
yield buckets
if buckets[-1] == N:
return
non_empty_buckets = sorted([i for i, count in enumerate(buckets) if count > 0])
if non_empty_buckets[-1] == K - 1:
temp = buckets[-1]
buckets[-1] = 0
buckets[non_empty_buckets[-2] + 1] = temp + 1
buckets[non_empty_buckets[-2]] -= 1
else:
buckets[non_empty_buckets[-1]] -= 1
buckets[non_empty_buckets[-1] + 1] += 1
这是 python 中的一个解决方案，它在 O(K) 内存和 O(# possible assignments) 时间内有效地产生 N 个球到 K 个桶的所有可能分配。
从一个所有球都在最左边的桶中的作业开始（为了理解，假设所有的桶都是从左到右排列的）。通过以下列方式将球逐渐向右移动来生成所有以后的分配：
(1) 如果最右边的球在最右边的桶中，则找到下一个最右边的球并将这两个球移到下一个最右边的球右侧的一个桶中 (2) 如果右边- 大多数球在其他任何地方，将其向右移动一桶
从这个方案中，可以清楚地看到为什么这只会产生独特的组合。需要更多思考才能了解为什么这会产生所有独特的组合。如果人们感兴趣，我可以尝试将证明形式化，但我现在跳过:)