假设我们有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很快.