用于选择阵列中半随机项的伪随机算法

Question

我有一个简单的数组(或者你喜欢的设置)整数,让我们把它称为X.我还有另一个数组W,它存储数组X中元素的"权重"."权重"表示第n个元素应该有多大的可能性被选中.现在我需要一种方法(算法)来(伪)根据数组W中定义的"权重"从数组/集合X中随机选择一个元素.

例如,如果我的W看起来像这样:W [0] = 2; W [1] = 4; W [2] = 6;

这意味着从数组X中选择第N项的概率为:X [0] = 16.6%X [1] = 33.3%X [2] = 50%

所以方法get_pseudorandom_item(X)应该在所有时间的一半左右返回第二项.

任何想法或建议如何实现(使用任何编程语言)非常感谢.谢谢.

Answer 1

1. 生成具有权重的部分和的数组P,即

   (P ₀ = W ₀),(P ₁ = W ₀ + W ₁),...,(P _n = W ₀ + W ₁ + ... + W _n)

   (你可以在W内做到这一点,实际上,如果你之后不需要权重).

2. 生成的随机数- [R [0,P _Ñ)其中P _Ñ表示最后一个这样的总和(即的总和所有的权重).

3. 找到索引ķ所述的最小的(第一)部分和更大的比你产生的数:

   P _ķ > ř  ∧∀ 一个 < ķ:P _一 < ř

4. 使用该索引选择您的实际元素:X _k