シャッフル

配列a[0],a[1],..,a[n]の要素をシャッフルしたい。

(つまり、シャッフル後、もともとa[i]にあった要素は等確率でa[0],a[1],..,a[n]のどれかにあることが条件)

次の方法はそれぞれ正しいだろうか?

(swapは要素の交換、rand(i,j)はiからjの整数を等確率で返す。)

(1)

for i = 0 to n
swap(a[i],a[rand(i,n)])

(2)

for i = 0 to n
swap(a[i],a[rand(0,n)])

正しいのは(1)。(2)が間違っているのは状態数がn^nであることから。

ちなみに(2)のアルゴリズムでシャッフル後a[n]の要素がa[0]にある確率は

¥frac{2}{n}¥left(¥frac{n-1}{n}¥right)^{n-1}

この確率を等確率の1/nで割ってn¥to¥inftyとすると

2¥left(¥frac{n-1}{n}¥right)^{n-1}¥to¥frac{2}{¥rm e}¥simeq 0.735758882

まぁ、後ろの要素が前にきにくいってことか?

More Reading
Newer//
Older// 相対的内部