O(1)加权随机选择与删除的算法

Question

我正在寻找一种权重随机选择算法，具有与别名方法类似的特性，只是选定后会将项目从集合中删除。

例如，我有一个袋子，其中产生：

- 70% 的概率为红色弹珠。 - 10% 的概率为绿色弹珠。 - 20% 的概率为蓝色弹珠。

我抽出一个红色弹珠。现在红色弹珠已经被移除，所以我认为这个袋子现在会产生：

- 33% 的概率为绿色弹珠。 - 66% 的概率为蓝色弹珠。

我相信您可以预先计算每个可能概率表的树形结构，因此样本仍然为 O(1)。是否有更聪明的算法来实现带有移除功能的常数时间加权选择？

- Matt Bierner

---

我还没有遇到过一种别名方法的变体，可以实现动态而有效地删除元素。我看到的最好选择是保持一组“已使用”元素，每当您遇到已使用的元素时重新抽样（如果您不会使用太多元素），或者存储元素的随机排列，并从该排列中删除（如果您将使用大量元素）。 - templatetypedef

Answer 1

实际上，我误读了问题。我不知道别名方法，下面的答案不是类似的算法。但因为这个回答仍然有用，所以我会把它留在这里。

---

我不知道有 O(1) 算法，但是可以用 log(N)² 的搜索和 log(N) 的更新轻松实现。使用更具体的算法可能会进一步优化。

将元素放入 树状数组 中，并将它们的概率作为值。同时，在更改元素时，保持总累积概率的跟踪。

现在我们不仅可以删除元素，还可以任意改变项目的概率，但是将某个项目的概率设置为 0 相当于删除它。然后，可以在 log(N) 的时间内查询第 n 个元素的累积概率。这在逻辑上扩展到对第一个累积概率大于 p 的元素进行 log(N)² 的二分搜索。

现在，为了进行带权随机选择，我们生成一个介于 0 和 P 之间（其中 P 是总累积概率）的数字 p。然后我们执行上面描述的二分搜索，以找到并选择第一个累积概率大于 p 的元素。

---

我对上述内容进行了改进，因为使用树状数组可以很容易地在 log(N) 的时间内搜索第一个累积概率大于或等于 p 的元素。我强烈建议阅读这篇关于树状数组的解释。

简单地说，要找到元素，在树状数组上执行常规的二分搜索，就像在任何其他树上一样，但是要保持当前累积和（从 0 开始）。每当您选择二分搜索的右侧子节点时，请将当前节点的值增加到当前累积和中。然后在比较当前节点的值和所寻找的累积和之前，将当前节点的值加到迄今为止的总和中。

- orlp

---

仍然很有趣。感谢您没有删除。 - sehe