私の目標は、0、... n-1 から k 個の整数を重複なくサンプリングすることです。サンプリングされた整数の順序は重要ではありません。各呼び出しごとに (非常に頻繁に発生します)、n と k はわずかに異なりますが、それほど大きくはありません (n は約 250,000、k は約 2,000)。私は、次の償却 O(k) アルゴリズムを思い付きました。
- 項目 0、1、2、...、n-1 を持つ配列 A を準備します。これには O(n) かかりますが、n は比較的安定しているため、コストを償却して一定にすることができます。
- [0:i] から乱数 r をサンプリングします。ここで、i = n - 1 です。ここで、コストは実際には n に関連していますが、n は非常に大きくないため、この依存関係は重要ではありません。
- 配列 A の r 番目の項目と i 番目の項目を入れ替えます。
- i を 1 減らします。
- ステップ 2 ～ 4 を k 回繰り返します。これで、A の末尾に長さ k のランダム順列ができました。これをコピーします。
- ステップ 1 のコストを一定に保つために、A を初期状態 (0、...、n-1) にロールバックする必要があります。これは、ステップ 2 の各パスで長さ k のスタックに r をプッシュすることで実行できます。スタックの準備には、償却された定数コストが必要です。
順列/組み合わせの均一なサンプリングは徹底的に研究された問題であるべきだと思うので、（1）はるかに優れた解決策があるか、少なくとも（2）私の解決策はよく知られている解決策（のマイナーな変更）です。したがって、
- (1)の場合、そのより良い解決策を知りたいです。
- (2)の場合は参考文献を探したい。
私を助けてください。ありがとう。