在 k 个 bin 中随机分配一个整数

Question

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

例如，allocate(4, 3)可以产生[4, 0, 0]、[0, 2, 2]、[1, 2, 1]等

每个项目应该随机分配，将每个 n 个项目随机分配到每个 k 个垃圾箱。

Answer 1

这是一个 brute-force 方法：

import numpy as np

def allocate(n, k):
    res = np.zeros(k)
    for i in range(n):
        res[np.random.randint(k)] += 1
    return res

Example:

for i in range(3):
    print(allocate(4, 3))

[0. 3. 1.]
[2. 1. 1.]
[2. 0. 2.]

Answer 2

当 n >> k:

时，这应该比您的 brute-force 版本更快

def allocate(n, k):
    result = np.zeros(k)
    sum_so_far = 0
    for ind in range(k-1):
        draw = np.random.randint(n - sum_so_far + 1)
        sum_so_far += draw
        result[ind] = draw
    result[k-1] = n - sum_so_far

    return result

我们的想法是抽取一个随机数，最大为某个最大值 m（开始等于 n），然后我们从最大值中减去该数字用于下一次抽取，然后以此类推，从而保证我们永远不会超过n。这样我们就可以填满前 k-1 个条目；最后一个填充了缺少的任何内容以获得恰好 n.

的总和

注意：我不确定这是否会导致值的“公平”随机分布，或者它是否会以某种方式偏向于将较大的值放入较早的索引或类似的东西中。

Answer 3

这是我的解决方案。我认为这将使所有可能的分配具有相同的可能性，但我没有这方面的证据。

from random import randint

def allocate(n,k):
    dividers = [randint(0,n) for i in range(k+1)]
    dividers[0] = 0
    dividers[k] = n
    dividers = sorted(dividers)    
    return [dividers[i+1]-dividers[i] for i in range(k)]
    
print(allocate(10000,100))

Answer 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) 选择 (k-1)) 种可能的分布，这同样有可能导致每一种分布。

（这是对 Wave Man 解决方案的一种修改：该解决方案在所有可能的解决方案中并不统一：请注意，获得 [0,0,4] 的唯一方法是滚动 (0,0)，但是有有两种获得 [1,2,1] 的方法；滚动 (1,3) 或 (3,1)。从 n+k-1 个槽中选择并计算分隔符作为一个槽可以纠正这个问题。在这个解决方案中，随机样本(1,2)对应[0,0,4]，等概率随机样本(2,5)对应[1,2,1])

Answer 5

根据 numpy 的新范式改编 Michael Szczesny 的：

def allocate(n, k):
    return np.random.default_rng().multinomial(n, [1 / k] * k)

This notebook verifies that it returns the same distribution as .

在 k 个 bin 中随机分配一个整数

Allocate an integer randomly across k bins

python

random