N个球在A个盒子中的组合枚举？

Question

我想要列举出N个球在A个箱子里的所有可能组合。

举个例子：我有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语言回答我，我将不胜感激。谢谢大家的贡献！

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

Answer 2

伪代码：

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)

Answer 3

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