带替换和不带替换的加权随机选择

为了应对编程挑战，我们寻求从列表中进行加权随机选择的有效算法，

带替换的加权选择

一种有效的方法带替换的加权选择是别名方法。该技术为每个加权元素创建一组相同大小的箱。通过利用位操作，我们可以有效地索引这些容器，而无需诉诸二分搜索。每个 bin 存储一个百分比，表示原始加权元素之间的边界。

考虑具有相等权重的五个元素的示例：(a, b, c, d, e)。

别名方法实现

1. 标准化权重：将每个权重除以总和即可1.0.
2. 确定大于或等于元素数量（此处为 8）的 2 的最小幂。
3. 为每个元素分配一个空分区。

4. 重复以下步骤，直到分配完所有权重：

   • 将尽可能多的剩余权重最小的元素放入空的元素中分区。
   • 如果分区未填充，则添加最重的剩余元素。

对于我们的示例，经过几次迭代后，我们有以下分区：

• p1: {a, 1.0}
• p2: {a, b, 0.6}

运行时选择

1. 生成0到1之间的随机数。
2. 对随机数进行位移位以找到分区索引。
3. 如果分区被分割，则使用移位数的小数部分来决定要分割哪个元素return.

无替换的加权选择

虽然存在像加权水库方法这样的算法来实现无替换的非加权选择，但这个问题仍未解决。