シャッフル

配列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)が間違っているのは状態数がであることから。

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

この確率を等確率ので割ってとすると

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