麻雀とかトランプとかで「バラバラにかき混ぜる」アルゴリズム。 偏らないように混ぜるには注意が必要。

仮に 0～x-1 の乱数（整数）を返す getRand(x) という関数があるとする。

良い例。

for(i = N - 1; i >= 1; i--) {
    n = getRand(i + 1);
    tmp = work[i];
    work[i] = work[n];
    work[n] = tmp;
}

ようは「N 個をかき混ぜたパターンは N! 通り」という点に注目。乱数の幅の積が N! の整数倍にならないアルゴリズムはアウト。

ただし乱数の質には要注意。普通に用意されている rand() などは質が悪いことが多い。

悪い例その 1。

for(i = 0; i < LOOP; i++) {
    n1 = getRand(N);
    n2 = getRand(N);
    tmp = work[n1];
    work[n1] = work[n2];
    work[n2] = tmp;
}

これだと初期配置の影響を受けやすい。

悪い例その 2。

for(i = 0; i < N; i++) {
    n = getRand(N);
    tmp = work[i];
    work[i] = work[n];
    work[n] = tmp;
}

惜しい。これは残念ながら一様分布にならない。