配列のシャッフル

a[N] = { 1, 2, ..., N }

っていうのを並べ替えたい時は、以下のようにしてやると効率が良く、数学的にもどの順列も等確率で生成される事が証明できる。

for (i = 0; i < N; i++) {
    swap(a[i], a[i〜N-1のどれかをランダムに選ぶ]);
}

これが恐らく一番良い方法の一つなので覚えておくと良い。

で、本題。

for (i = 0; i < N; i++) {
    bool ok;
    v = 1〜Nの数をランダムに生成;
    do {
        ok = true;
        for (k = i - 1; k > 0; k--) {
            if (a[k] == v) {
                ok = false;
                break;
            }
        }
    } while (!ok);
    a[i] = v;
}

こんな風に書いちゃう大学生もいるんだけど、これは効率が悪い。頑張って計算してみたら平均回かかることがわかた。N=1000の時に平均7000回位なのでまぁ許せると言えば許せるけど、運ゲーなのでたまに恐ろしい時間はまってしまう危険性もある。と言うわけで最初に書いた方を使うようにしましょう。std::random_shuffleをつかっとけと。