假设我们要选择 的随机排列{1,2,...,n}，但p(i)元素i的概率为正，并且i排列中第一个元素的概率为p(i)，然后如果i选择第一个元素，则排列中第二个元素的概率为j是p(j) / (1 - p(i))，依此类推，其中m在给定位置选择元素的概率始终与 成正比p(m)。生成随机排列的有效方法是什么？O(log n)天真地，我们可以在计算 的累积和之后及时选择第一个元素p(i)，但是如果选择的元素在列表的中间，那么更新概率的累积和需要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)在当前选择的集合中，然后从最大的开始更新累积和，然后p(i)向后移动删除所选元素并更新累积和，p(i)直到未选择元素的总和p(i)高于未删除元素的累积总和的一部分。这种或另一种策略是否提供了预期的O(n log n)时间？有人可以填写详细信息吗？