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

Question

我想编写一个函数，生成一个元组数组，其中包含 C++ 中 M 个盒子中 N 个球的所有可能排列。

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

网上没找到这样的C++实现，只有char的排列或者排列个数的计算...

有什么想法吗？

Answer 1

有一个巧妙的技巧可以解决这个问题。想象一下，我们拿了 n 个球和 m - 1 个盒子，并将它们排成一排，长度为 n + m − 1(箱子混在球中)。然后将每个球放入其右侧的盒子中，并在右侧添加第 m 个盒子，用于放置剩余的所有球。

这会在 m 个盒子中产生 n 个球的排列。

很容易看出，n 个球与 m − 1 个盒子(第一张图片)的排列数量与排列的数量相同n 个球在 m 个盒子里。 (要走一条路，将每个球放在右边的盒子里；要走另一条路，每个盒子将球清空到它左边的位置。)第一张图片中的每个排列都由我们放置的位置决定盒子。有 m − 1 个框和 n + m − 1 个位置，所以有 ^{n + m − 1}C_{m − 1} 种方法。

所以你只需要一个普通的组合算法(see this question)来生成盒子的可能位置，然后取连续位置之间的差异(减去 1)来计算每个盒子中的球数。

在 Python 中它会非常简单，因为有一个 combinations标准库中的算法:

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,)))