C++中M盒中N个球的组合列表

Question

我想编写一个函数来生成一个元组数组,其中包含C++中M个框中所有可能的N个球的排列.

顺序(编辑:在结果列表中)并不重要,只是第一个必须是(N,0,...,0)和最后一个(0,0,...,N).

我没有在C++网上找到这样的实现,只有字符的排列或排列数的计算......

有任何想法吗 ？

Answer 1

解决这个问题有一个巧妙的技巧.想象一下,我们把n个球和m  - 1个盒子放在一排长度为n  +  m  - 1 的行中(盒子在盒子中混合).然后将每个球放在右侧的方框中,并在右侧添加一个第m个方框,以获得剩下的任何球.

这产生了m个盒子中的n个球的排列.

这是很容易看到,有相同数量的安排Ñ与序列球米  - 1个箱(第一图片),因为有安排Ñ在球米框.(换一种方式,将每个球放在右边的方框中;另一方面,每个方框将球排空到左边的位置.)第一张图中的每个排列由我们放置的位置决定.框.有m  - 1个盒子和n  +  m  - 1个位置,因此有^{n  +  m  - 1} C _{m  - 1个}方法可以做到这一点.

所以你只需要一个普通的组合算法(参见这个问题)来生成盒子的可能位置,然后取连续位置之间的差异(小于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,)))