algorithm - 选择具有元素权重的随机排列

Question

假设我们要选择 {1,2,...,n} 的随机排列，但在元素 上具有正概率 p(i) >i，并且i是排列中第一个元素的概率是p(i)，那么如果i被选为第一个元素，则排列中第二个元素为 j 的概率为 p(j)/(1 - p(i))，依此类推，其中在给定位置选择元素 m 的概率始终与 p(m) 成正比。生成随机排列的有效方法是什么？天真地，我们可以在计算完 p(i) 的累积和后，在 O(log n) 时间内选择第一个元素，但是如果选择的元素在列表中间然后更新概率的累积和需要 O(n) 时间，导致 O(n^2) 算法。

我的一个想法是，如果所有的 p(i) 都与 1/n 成正比(在有界常数因子内)，那么我们可以实现预期的 O(n log n) 时间允许重复一段时间(如果获得重复则重新绘制)，直到到目前为止所选元素的概率总和超过 1/2。然后删除所有选中的元素并更新剩余未选中元素的 p(i) 的累积和。但是，如果元素的概率是无序的并且非常倾斜，例如 1/2,1/4,1/8...，这将不起作用。但是转念一想，如果我们在计算累加和之前将i按照p(i)递增排序，采用类似的策略，当所选元素的 p(i) 超过了当前集合中 p(i) 总和的一部分，然后从最大的 开始更新累积总和code>p(i) 并向后删除所选元素并更新 p(i) 的累积和，直到 p(i) 未选择元素的总和高于未删除元素的累积和的某个分数。这个或另一个策略是否给出了预期的 O(n log n) 时间？有人可以填写详细信息吗？

Answer 1

您实际上是在寻找这个问题的答案:"What is a good datastructure to keep cumulative values in?"

有两个答案导致O(n log n) 算法。 One answer提出了一个二叉树，它另外跟踪所有子节点的总和。 Another answer提及 Cumulative Frequency Tables这基本上是相同的想法。