arrays - 用于选择数组中的半随机项的伪随机算法

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_>1 = W₀ + W₁), ..., ( P_n = W₀ + W₁ + ... + W_n)

   (实际上，如果之后不需要权重，您可以在 W 内执行此操作)。

2. 在[0, P_n)中生成一个随机数r，其中 P_n 表示最后一个这样的总和(即所有权重的总和)。

3. 找到最小(第一个)部分和大于您生成的数字的索引k:

   P_k> r ∧ ∀ a <k : P_a <r

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