的元素选择一个随机排列配重块

Question

假设我们要选择的{1,2,...,n}随机排列，但元素i正面的概率p(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...。但后来我想，如果我们在计算累计和之前按照p(i)增加i，并且遵循类似的策略，并且当所选元素的总和超过当前集中的p(i)之和的一部分时然后更新从最大的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这基本上是一样的想法。