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

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]); } ぱっと見て違いが分かる？ イン

[akkun_choi]

前者はn^n、後者はn!。前者だと同じキーが再度選ばれる可能性がある

[saz_go]

配列の中身をランダムな順序にシャッフルするコード

[mohno]

いやー、知らなかった（読んだことがあっても忘れていた）。

[sigwyg]

ランダムソートの気づきにくい偏り

[uunfo]

二つだけで考えてもおかしいね　http://www.codinghorror.com/blog/archives/001015.html

[y-kawaz]

ランダムオーダーでソートとか、そもそもshuffle関数を探す。

[paella]

カルドセプト問題と同種と捉えて、その深刻さに気づいておかないと。。

[malibu-bulldog]

常に意識したい事。

[shidho]

VC++5のStandard Template Libraryのシャッフルは前者らしい。

[smoking186]

http://b.hatena.ne.jp/entry/842643 と http://b.hatena.ne.jp/entry/857120

[taninsw]

後者の方はカードをランダムに1枚づつ抜いて並べていくのと一緒かな。配列ひとつでやってるから分かりにくいけど。/前者の方法がどれだけ偏るのか気になるので後で元ネタ読む

[korinchan]

同じ配列内ではなく、別の配列にシャッフルし直すところから考えれば間違えることはないと思う。

[FTTH]

「分かりやすくて間違いの無い」が優先されるなら「単純でいいから」は変な気がする。「偏りがあっても単純なコード」または「分かりやすくて間違いの無いコード、単純なら理想的」でないかな。本題じゃないけど。

[imo758]

シャッフルなのにrand.Next(cards.Length)の時点でものすごく違和感

[SiroKuro]

全然分からない……

[mtsuyugu]

正しい方のやり方は知ってはいたが「なぜ」を考えることはなかった。なるほどね。

[o_show]

単純なカードシャッフルのアルゴリズムは、偏りがあった！