ランダムに並び替える

Coding Horror: The Danger of Naïveté
ランダムに並び替えるアルゴリズムについて。記事の頭にのっているサンプルコードは次のとおり。

for (int i = 0; i < cards.Length; i++)
{
    int n = rand.Next(cards.Length);
    Swap(ref cards[i], ref cards[n]);
}

でもこのコードでは問題あり。シャッフル後に偏りが出てしまう。正しいコードは次のとおり。

for (int i = cards.Length - 1; i > 0; i--)
{
    int n = rand.Next(i + 1);
    Swap(ref cards[i], ref cards[n]);
}

これはKnuth-Fisher-Yates shuffle algorithmというらしい。

そういえば以前、自分も似たような日記を書いた記憶が。
[id:toburau:20080711]
[id:toburau:20080712]
http://ch.cri-mw.co.jp/iwai/52290.htmlで添削してもらったコードが似たようなコードになっている。そっちは配列の先頭から決定していく感じ。

ただシャッフルするだけでも奥が深いなぁ。

via 単純で正しそうなものが正しいとは限らない - Radium Software