シャッフルについて

http://www.hyuki.com/d/200510.html#i20051020190000

以下、サイズをsとする。
正しいシャッフルは長さsの置換全体（対称群）からランダムに選ばなければならない。

void shuffle(int music[], int size)
{
    int i;
    for (i = 0; i < size; i++) {
        int r = random(0, size);
        int m = music[i];
        music[i] = music[r];
        music[r] = m;
    }
}

このプログラムはi step目でmusic[i]とmusic[r]を置き換えている。ということはs step終了時にはs回の互換が行われている。
従ってsが偶数なら偶置換のみ, sが奇数なら奇置換のみが行われる。よって、これは完全なシャッフルでは無い。以上。

嘘。間違えた。自分自身との交換があるので、偶置換も奇置換も取り得る。
正しくは以下か。
i step目でrが取る値をr_iとする。するとr_iの取り方はs^s通り。一方、長さがsの対称群の要素数は1-sまでの順列と考えてよいので、s!通り。s ≧ 3のときs^s/s!は割り切れないので等確率で取れていないことになる。

本当にシャッフルしたいならば、i step目で長さがiの置換からランダムに選んでおいて、その0〜i-1とiをランダムに入れかえればいいわけか。成る程。