のランダム順列を選択したいとしますが、要素の{1,2,...,n}確率は正であり、順列の最初の要素である確率はであり、次に が最初の要素として選択された場合、順列の 2 番目の要素である確率はなどで、特定の位置で要素が選択される確率は常に に比例します。ランダム順列を生成する効率的な方法は何ですか? 素朴に、の累積和を計算した後に時間内の最初の要素を選択できますが、選択した要素がリストの中央付近にある場合、確率の累積和を更新するにはp(i)iip(i)ijp(j) / (1 - p(i))mp(m)O(log n)p(i)O(n)時間、O(n^2)アルゴリズムにつながります。
私が考えていたのは、すべてが（制限された定数係数内で）p(i)比例している場合、選択された要素の確率の合計が得られるまで、しばらくの間重複を許可することで期待される時間を達成できるということでした（重複が得られた場合は再描画するだけです）。 1/2をはるかに超えています。次に、選択したすべての要素を削除し、選択されていない残りの要素の累積和を更新します。しかし、要素の確率が順不同で非常に歪んでいる場合、これは機能しません。しかし、累積合計を計算する前に に従って昇順に並べ、同様の戦略に従い、選択した要素の合計が1/nO(n log n)p(i)1/2,1/4,1/8...ip(i)p(i)p(i)選択されている現在のセットで、最大のものから始めて累積合計を更新し、p(i)選択された要素を削除し、選択されていない要素の合計が削除されていない要素の累積合計の一部を超えるp(i)まで累積合計を更新します。p(i)この戦略または別の戦略で予想されるO(n log n)時間が得られますか? 誰か詳細を記入できますか？