プログラミングパールから:コラム12:サンプル問題:
入力は 2 つの整数mとnで構成され、 m < nです。出力は、範囲0..n-1のm 個の乱数整数のソートされたリストであり、整数が 2 回以上出現することはありません。確率バフの場合、各選択が等しい確率で発生する置換なしのソートされた選択が必要です。
著者は 1 つの解決策を提供します。
initialize set S to empty
size = 0
while size < m do
t = bigrand() % n
if t is not in S
insert t into S
size++
print the elements of S in sorted order
上記の疑似コードでは、大きなランダムな整数 ( mおよびnbigrand()
よりもはるかに大きい) を返す関数です。
上記のアルゴリズムの正しさを証明するのを手伝ってくれる人はいますか?
私の理解によれば、すべての出力には 1/C( n , m ) の確率が必要です。上記のアルゴリズムが 1/C( n , m ) の確率で出力を保証できることを証明するにはどうすればよいですか?