array[0], array[1], ... , array[N-1]
をランダムにシャッフルする方法。
rand(n) は 0, 1, ..., n-1 の n 個の値をランダムに返す関数とする。
for(i = 0; i < N - 1; i++){
a = rand(N - i);
swap(array[i], array[i + a]);
}
配列の並び方は N! 通りです。この並びは、N 個の中から１つ選び、残りの中から１つ選び・・・、という処理を続けていくことで全て得られます。上のコードはまさにそれをしています。
ちなみに、次のようにしても同様です。STL の random_shaffle と似た感じの方法です。
for(i = 1; i < N; i++){
a = rand(i + 1);
swap(array[i], array[a]);
}
このコードは、先程のコードの i を変化させる向きを逆にしただけです。処理が直感的でないので確率を計算してみましょう。
配列の末尾に k 番目の要素が来るには、最後の swap で k 番目の要素が選ばれるしかないので、確率は k によらず 1 / N になります。末尾から２番目に k 番目の要素が来るのは、k < N - 1 の場合、最後の１つ前の swap で選ばれ、最後に選ばれない確率なので (1 / (N - 1)) * ((N - 1) / N) = 1 / N になり、k = N の場合、最後の swap で N - 1 が選ばれる確率なので 1 / N になります。以下帰納的に、全ての要素についてシャッフル後に配列のどこに現れる確率も 1 / N であることを証明できます。
慣れればこっちの方がスッキリしていていいかもしれません。減算が１つ少ないですしね。
最終更新：2012年11月13日 14:36
