生成n个仓中k个球的所有可能结果(多项式/分类结果的总和) [英] Generate all possible outcomes of k balls in n bins (sum of multinomial / categorical outcomes)

问题描述

假设我们有n个容器，其中要扔k个球.什么是快速(即使用numpy/scipy代替python代码)生成所有可能结果作为矩阵的方式?

Suppose we have n bins in which we are throwing k balls. What is a fast (i.e. using numpy/scipy instead of python code) way to generate all possible outcomes as a matrix?

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

For example, if n = 4 and k = 3, we'd want the following 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

很抱歉，如果没有任何排列，但这是一般的想法.生成的排列不必按任何特定顺序排列，但是上面的列表便于从精神上对其进行分类迭代.

Apologies if any permutation was missed, but this is the general idea. The generated permutations don't have to be in any particular order, but the above list was convenient for categorically iterating through them mentally.

更好的是，还有一种方法可以将每个整数从1映射到多集数字(此列表的基数)直接指向给定的排列?

Better yet, is there a way to map every integer from 1 to the multiset number (the cardinality of this list) directly to a given permutation?

此问题与以下问题有关，这些问题在R中以非常不同的功能实现:

This question is related to the following ones, which are implemented in R with very different facilities:

• 生成M个垃圾箱中N个球的所有排列
• 生成所有可能的结果矩阵，以掷出n个骰子(忽略顺序)

• 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

• 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

推荐答案

这是使用itertools.combinations_with_replacement的生成器解决方案，不知道它是否适合您的需求.

Here's a generator solution using itertools.combinations_with_replacement, don't know if it will be suitable for your needs.

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]]

此函数的复杂性呈指数增长，因此在可行与否之间存在离散的界限.

The complexity of this function grows exponentially, so there is a discrete boundary between what is feasible and what is not.

请注意，虽然numpy数组在构造时需要知道其大小，但由于可以轻松找到多集数，因此这很容易实现.在可能以下是更好的方法，我没有做任何计时.

Note that while numpy arrays need to know their size at construction, this is easily possible since the multiset number is easily found. Below might be a better method, I have done no timings.

from math import factorial as fact
from itertools import combinations_with_replacement as cwr

nCr = lambda n, r: fact(n) / fact(n-r) / fact(r)

def partitions(n, b):
    partition_array = numpy.empty((nCr(n+b-1, b-1), b), dtype=int)
    masks = numpy.identity(b, dtype=int)
    for i, c in enumerate(cwr(masks, n)): 
        partition_array[i,:] = sum(c)
    return partition_array

这篇关于生成n个仓中k个球的所有可能结果(多项式/分类结果的总和)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！