python – 在n个bin中生成k个球的所有可能结果(多项式/分类结果的总和)

假设我们有n个投掷k球的箱子.什么是快速(即使用numpy / scipy而不是python代码)方式来生成所有可能的结果作为矩阵?

例如,如果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

解决方法:

出于参考目的,以下代码使用Ehrlich’s algorithm来迭代C,Javascript和Python中多集的所有可能组合:

07001

这可以使用this method转换为上述格式.具体来说,

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

这仍然不是纯粹的numpy,但可以用来填充预分配的numpy.array很快.

上一篇:c – 在CPP中重复的n个字符的长度为k的所有排列


下一篇:c-使用ASCII值确定A是否为B的置换