的元素選擇一個隨機排列配重塊

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這基本上是一樣的想法。