3

プログラミングパールから：コラム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 ) の確率で出力を保証できることを証明するにはどうすればよいですか?

4

1 に答える 1

1

このアルゴリズムが生成する各ソリューションは有効です。

ソリューションはいくつありますか? 最後の行まで (ソート)n*(n-1)*(n-2)*..*(n-m)順列が異なるか
n!/(n-m)!、各結果が同じ確率である

並べ替えると、可能な解の数が m! 減ります。

したがって、可能な出力の数はn!/((n-m)!*m!)、これがあなたが求めたものです。

n!/((n-m)!m!) = C(n,m)

于 2012-07-29T08:44:13.193 に答える