python - 在 k 个容器中随机分配一个整数，并在分配中均匀分布

Question

我正在寻找一个高效的 Python 函数，它可以在 k 个容器中随机分配一个整数。也就是说，某些函数 allocate(n, k) 将生成一个 k 大小的整数数组，总和为 n。

例如，allocate(3, 2) 会产生 [3, 0], [2, 1], [1, 2] 或 [0, 3] 等概率(与 Allocate an integer randomly across k bins 不同，分配而不是项目应该均匀分布)。

Answer 1

使用“星形和条形”方法，我们可以将其转化为从 n+k-1 个可能位置的列表中为可能的分隔符选择 k-1 个位置的问题。 ( Wikipedia proof )

from random import sample

def allocate(n,k):
    dividers = sample(range(1, n+k), k-1)
    dividers = sorted(dividers)
    dividers.insert(0, 0)
    dividers.append(n+k)
    return [dividers[i+1]-dividers[i]-1 for i in range(k)]
    
print(allocate(4,3))

有 ((n+k-1) choose (k-1)) 种可能的分配符合您的标准，每一种分配都对应于选择 k 个位置的特定方式，将分隔线放在对象的 n+k-1 个位置中，这同样有可能导致它们中的每一个。

(请注意评论中提议的细微差别 existing answer to a similar question:这个问题要求非负整数的有序序列，而提议的答案给出正整数的有序序列。选择的天真修改有替换而不是没有替换的点确实允许完整的非负整数分布集，但它不会使每个分布具有相同的可能性。考虑分配(4,3):获得 [0, 0, 4] 的唯一方法就是滚动(0, 0)，但是滚动(1, 3) 或(3, 1) 可以得到[1, 2, 1]。