代码之家 › 专栏 › 技术社区 › Max Ghenis shoyer

在k个容器中随机分配一个整数,在分配中均匀分布

random python

1

Max Ghenis shoyer · 技术社区 · 4 年前

我正在寻找一个高效的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 ,而不是项目,应该统一分配)。

1 回复 | 直到 4 年前

1

2

Richard Yannow 4 年前

使用“星条旗”方法,我们可以将其转化为一个问题,即从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)在每个可能的分配中,选择n-k+1的分配可能是每个分配中的一个。

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