C框中M个框中N个球的组合列表 [英] List of combinations of N balls in M boxes in C++

问题描述

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

I would like to write a function that generate an array of tuples containing all possible permutations of N balls in M boxes in C++.

结果列表）不重要，只是第一个必须是（N，0，...，0）和最后一个（0,0，...，N）。

The order (Edit : in the resulting list) is not important, just that the first must be (N,0,...,0) and the last (0,0,...,N).

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

I didn't find such an implementation on the net in C++, only permutations of chars or calculations of the number of permutations...

任何想法？

推荐答案

有一个很好的解决方法。想象一下，我们把 n 个球和 m - 1个方块放在一行长度 n + m - 1（球之间的盒子混在一起）。然后将每个球放在右边的盒子中，并在右边添加一个第

There's a neat trick to solving this. Imagine that we took the n balls and m − 1 boxes and put them in a row of length n + m − 1 (with the boxes mixed up among the balls). Then put each ball in the box to its right, and add an mth box at the right that gets any balls that are left over.

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

This yields an arangement of n balls in m boxes.

很容易看出， n 球的顺序与 m - 1个框第一图片），因为在 m个框中有 n 个球的排列。 （一种方式，把每个球放在盒子里它的右边;换句话说，每个盒子将球清空到其左边的位置。）第一张图片中的每个排列由我们放置的位置决定框。有 m个 - 1个框和 n + m - 1个位置，因此有 ^{n < m - 1} C - 1 种方式。

It is easy to see that there are the same number of arrangements of n balls in sequence with m − 1 boxes (the first picture) as there are arrangements of n balls in m boxes. (To go one way, put each ball in the box to its right; to go the other way, each box empties the balls into the positions to its left.) Each arrangement in the first picture is determined by the positions where we put the boxes. There are m − 1 boxes and n + m − 1 positions, so there are ^{n + m − 1}C_m − 1 ways to do that.

因此，您只需要一个普通的组合算法（查看此问题）生成框的可能位置，然后取连续位置之间的差异（小于1）以计算每个框中的球数。

So you just need an ordinary combinations algorithm (see this question) to generate the possible positions for the boxes, and then take the differences between successive positions (less 1) to count the number of balls in each box.

在Python中，这将非常简单，因为有一个标准库中的组合算法：

In Python it would be very simple since there's a combinations algorithm in the standard library:

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

这篇关于C框中M个框中N个球的组合列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！