在n个箱子中生成k个球的所有可能结果（多项式/分类结果之和）

Question

假设我们有n个箱子，我们在其中扔k个球。以矩阵形式生成所有可能的结果的方法是什么？在

例如，如果n = 4和k = 3，我们需要以下numpy.array：

3 0 0 0
2 1 0 0
2 0 1 0
2 0 0 1
1 2 0 0
1 1 1 0
1 1 0 1
1 0 2 0
1 0 1 1
1 0 0 2
0 3 0 0
0 2 1 0
0 2 0 1
0 1 2 0
0 1 1 1
0 1 0 2
0 0 3 0
0 0 2 1
0 0 1 2
0 0 0 3

抱歉，如果错过了任何排列，但这是一般的想法。生成的排列不必按任何特定的顺序排列，但上面的列表便于在头脑中对它们进行分类迭代。在

更好的是，有没有办法将从1到multiset number（这个列表的基数）的每个整数直接映射到给定的排列？

这个问题与以下问题有关，这些问题在R中使用的设施非常不同：

• Generating all permutations of N balls in M bins
• Generate a matrix of all possible outcomes for throwing n dice (ignoring order)

相关参考文献：

• https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
• https://en.wikipedia.org/wiki/Multiset#Counting_multisets
• https://en.wikipedia.org/wiki/Combinatorial_number_system

Answer 1

为了参考，下面的代码使用Ehrlich's algorithm迭代遍历C++、JavaScript和Python中的多个集合的所有可能组合：

https://github.com/ekg/multichoose

可以使用this method将其转换为上述格式。具体来说

for s in multichoose(k, set):
    row = np.bincount(s, minlength=len(set) + 1)

这仍然不是纯粹的numpy，但是可以很快地填充预先分配的numpy.array。在