在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

这是一个简单的实现，使用列表理解，与numpy相比，不确定性能

def gen(n,k):
    if(k==1):
        return [[n]]
    if(n==0):
        return [[0]*k]
    return [ g2 for x in range(n+1) for g2 in [ u+[n-x] for u in gen(x,k-1) ] ]

> gen(3,4)
[[0, 0, 0, 3],
 [0, 0, 1, 2],
 [0, 1, 0, 2],
 [1, 0, 0, 2],
 [0, 0, 2, 1],
 [0, 1, 1, 1],
 [1, 0, 1, 1],
 [0, 2, 0, 1],
 [1, 1, 0, 1],
 [2, 0, 0, 1],
 [0, 0, 3, 0],
 [0, 1, 2, 0],
 [1, 0, 2, 0],
 [0, 2, 1, 0],
 [1, 1, 1, 0],
 [2, 0, 1, 0],
 [0, 3, 0, 0],
 [1, 2, 0, 0],
 [2, 1, 0, 0],
 [3, 0, 0, 0]]

Answer 2

为了参考，下面的代码使用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。在

Answer 3

这里有一个使用itertools.combinations_with_replacement的生成器解决方案，不知道它是否适合您的需要。在

def partitions(n, b):
    masks = numpy.identity(b, dtype=int)
    for c in itertools.combinations_with_replacement(masks, n): 
        yield sum(c)

output = numpy.array(list(partitions(3, 4)))
# [[3 0 0 0]
#  [2 1 0 0]
#  ...
#  [0 0 1 2]
#  [0 0 0 3]]

这个函数的复杂度呈指数增长，所以在可行和不可行之间存在一个离散的边界。在

注意，虽然numpy数组在构造时需要知道它们的大小，但这很容易实现，因为多集数很容易找到。下面的可能是一个更好的方法，我没有做计时。在

^{pr2}$