在 k 个 bin 之间随机分配一个整数，并在分配之间均匀分布

Question

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

例如，allocate(3, 2)会以相同的概率生成[3, 0]、[2, 1]、[1, 2]、 或[0, 3]（与在 k 个 bin 之间随机分配整数不同，分配而不是项目应该均匀分布）。

Answer 1

使用“星形和条形”方法，我们可以将其转化为从 n+k-1 个可能位置的列表中为可能的分隔符选择 k-1 个位置的问题。（维基百科证明）

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) 选择 (k-1)) 种符合您标准的可能分配，每种分配对应于选择 k 个位置以将分隔线放置在 n+k-1 个对象位置之间的特定方式，并且此导致其中每一个的可能性是相同的。

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