枚举将N个球放入A个盒子的组合？

Question

枚举将N个球放入A个盒子的组合？

4

我希望能够列举出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语言回答我的问题，我将不胜感激。感谢所有的贡献！

- sol

8个回答

5

伪代码：

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)

- Toon Krijthe

简单、优雅和递归... +1 :) - Paulo Santos

sol: 我还在努力理解 :oD用Python编写时，它并没有枚举所有可能性，所以我正在寻找我的错误所在...def Enumerate(Balls, Boxes, box): if Boxes <= 0: print "错误" elif Boxes == 1: box[0] = Balls print Boxes else: for b in range(Balls): print b box[Boxes - 1] = b Enumerate(Balls - b, Boxes - 1, boite) print box return

主函数

Boxes = 3 Balls = 2 box = [0] * 3 print box Enumerate(2, 3, box) - sol

5

请不要使用伪代码。我认为您的解决方案是错误的，但实际上我无法批评它，因为我不理解Box [1] = Balls的含义。您的伪数组是1索引还是0索引？"Box"是什么意思？"PrintBoxes"是做什么用的？ - Glyph

2

请参考Python 3.1中的itertools.combinations_with_replacement进行示例编写。此外，在组合数学中，通常将带替换的组合问题转化为不带替换的组合问题，这在2.6的itertools中已经内置。这种方法的优点是不会生成像基于product或permutation的解决方案中那样的被丢弃的元组。以下是使用标准（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)]

- A. Coady

1

使用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

- Evgeny Pogorelov

1

您可以定义一个递归的生成器，为您希望嵌套的每个“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'参数，其他参数是默认值，以便递归调用可以传递不同的内容。它将生成整数元组（长度为'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)))

- Glyph

0

如果你只是想知道可能性的数量，而不是列出它们，那么以下公式可以解决：

可能性 = (N+A-1) C N = (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。如果我在教你如何吃鸡蛋，对不起。

在Python中：

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个盒子，有超过3百万种可能性！编辑：我的先前答案将此问题与整数划分进行比较，以显示可能性数量增长得多快。我的新答案与原始问题更相关。

- Alasdair

0

如果您想使用自己的函数，则Gamecat提供的答案可能有效。

否则，可以使用http://probstat.sourceforge.net/，它非常快（用c编写）。

或者可以在Python 2.6中使用itertools。

-

0

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解决方案，可以高效地将N个球分配到K个桶中，并且在O(K)的内存和O(#可能的分配)的时间内产生所有可能的分配。

从一个分配开始，其中所有球都在最左边的桶中（为了理解起见，假设所有桶都从左到右排列）。通过以下方式逐步将球向右移动来生成所有后续分配：

(1) 如果最右边的球在最右边的桶中，则找到下一个最右边的球，并将这两个球移动到下一个最右边的球右侧的桶中。 (2) 如果最右边的球在其他任何位置，则将其向右移动一个桶。

从这个方案中，很清楚可以看出为什么只会生成唯一的组合。要想看到为什么这会产生所有唯一的组合，需要更多的思考。如果有人感兴趣，我可以尝试正式证明，但现在我跳过 :)

- robertsami

我尝试遍历生成器iterate_assignments(3,2)，但在buckets[non_empty_buckets[-2] + 1] = temp + 1处出现了“IndexError: list index out of range”的错误。 - 14wml

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，

- SilentGhost · Accepted Answer

这段代码从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)}