4

私は整数1、2、3、...、nを持っており、そこからm<n個の異なる整数をランダムに選択する必要があります。これらの整数を配列に入れてから、FisherYatesShuffleを使用するつもりです。

配列内のエントリをランダムに選択します。最後のエントリと交換します。次に、最後のエントリを除いて、配列内のエントリをランダムに選択します。これを最後から2番目のエントリと交換します。この方法で最後のmエントリが取得されるまで繰り返します。

質問

私の理解では、n回まで続けると、このシャッフルですべての可能な配置が同じように発生する可能性があります。したがって、m <n回後に停止した場合、最後のmエントリのすべての配置が同じように発生する可能性があります。したがって、最後のm個のエントリは、必要なm個のランダムな個別の整数です。

私の理解は正しいですか?

4

1 に答える 1

3

はい、おそらく前進するのは簡単です:

rand(z)範囲内に戻りましょう[0..z)

for (int i = 0; i < m; i++)
    swap(X[i], X[i+rand(n-i)])

X[0..m-1]ランダムサンプルになりました

于 2012-11-24T17:12:52.890 に答える