Can you trust Random?

メンバーのデバッグを手伝ってるうちに、頭の痛くなるようなコードを見つけたのでシェア。

そのコードは簡単に言うと、トランプで例えるとカードをよく切って1枚ずつ配っていくようなもの。

もちろん1枚しかないカードを2回配ることはできないから、そのカードがすでに配られたかどうかを判定しなければならない、とでも思ったのだろう。

加えて、トランプデッキの数も変わる(例えば2セットだったら全部で104枚のカードになる)というから、今そのカードが何枚あるかも保持しておきたい。

そんな訳でできたコードがこれ。

void init(int numberOfDeck){
    // デッキを初期化
    for(i = 0; i<52; i++){
        card[i] = numberOfDeck;
    }
}

Random r = new Random();
Card getCard(){
    int x;
    do{
        x = r.nextInt(52);
    } while(card[x] == 0); // 枚数0だったらやり直し

    card[x]--; // 一枚引く。
    return new Card(x); // xに応じてなんか返す。
}

頭痛い。

だって、最初の1枚はどれ引いても当たりだけど、乱数rが最後の1枚引く確率は1/52ですよ。その分ループ回数も多くなるし、非効率すぎる。

さらに乱数なんだから延々最後の1枚がでないってこともありうるし。仕事でこんなコード書いたら切れられる。いや、誰にかはわかりませんが。

プロジェクトの極一部でしか使われていないコードだからそんなに影響もないんだろうけど、今度こっそり修正しとこうかな。

ちなみに重複なしでランダムなカードを配るというときは最初にすべての配列を作っておいて(2セットなら104個)、それをシャッフルした後に最初から順番に配っていくというのが王道だと思います。

選ぶときに乱数を生成するんでなくて、シャッフル時に乱数を使うというのがミソ。配るときには結局配列を総なめしてるだけなのでアルゴリズムのオーダーはO(n)で済みます。

シャッフルするにも普通に乱数使うと偏ってしまうので、ちょっとだけ工夫します。こちらに実装例がありました。wikipediaならこちらです。

このアルゴリズムの考え方としてはn個の配列からはn!の順列組み合わせが作れるので、シャッフルされた配列がちょうどn!分の1の確率で出るようになればいいわけです。

このアルゴリズムでは最初の1枚は1/nの確率で選ばれます。次の1枚は1/(n-1)の確率で、その次は1/(n-2)の確率でってやっていくと、最終的に選ばれる配列の確率は1/n * 1/(n-1) * ... * 1/1 = 1/(n!)ということでn!分の1になるのでした。

おそまつさまでした。