C言語/C++で配列をシャッフルする（ランダムに並び替える）方法

C言語やC++でのプログラミング中、配列をランダムにシャッフルしたい、と思ったことは誰しも一度はあるのではないでしょうか。しかし具体的にどうシャッフルすればよいのか？下手な方法だと完全にシャッフルできていなかったり、無駄に時間がかかったりします。

本記事ではSTLを使う場合とそうでない場合に分けて解説します。

C++の場合（STLを使う場合）
C言語の場合（STLを使わない場合）
- シャッフルの手順
まとめ

C++の場合（STLを使う場合）

STLのalgorithmライブラリにstd::shuffleという関数がC++11から導入されました。これを用いることによりvectorの要素をシャッフルできます（vectorだけでなくarrayやstringもシャッフルできます）。

まず必要なライブラリをインクルードします。

#include <random>
#include <algorithm>
#include <vector>

vecというvectorをシャッフルするには以下のようにします。

std::mt19937 get_rand_mt;
std::shuffle( vec.begin(), vec.end(), get_rand_mt );

64bit環境では以下。

std::mt19937_64 get_rand_mt; // 64bit版メルセンヌ・ツイスタ
std::shuffle( vec.begin(), vec.end(), get_rand_mt );

ここでstd::mt19937やstd::mt19937_64というのは乱数を生成するクラスです。質の良い擬似乱数で動作も高速と言われるメルセンヌ・ツイスタを用いた乱数生成器で、C++11からSTLに導入されました。

また、乱数のseedを指定したい場合はコンストラクタの引数に値を渡します。

std::mt19937 get_rand_mt(0); // seedに0を指定
std::shuffle( vec.begin(), vec.end(), get_rand_mt );

メルセンヌ・ツイスタは擬似乱数であり推測が可能な場合もあるので、ゲームなどで予測されては困る場合は以下のようにseedに乱数を指定しましょう。

std::random_device get_rand_dev;
std::mt19937 get_rand_mt( get_rand_dev() ); // seedに乱数を指定
std::shuffle( vec.begin(), vec.end(), get_rand_mt );

std::random_deviceはメルセンヌ・ツイスタとは違い、ハードウェアの情報を用いた本当の意味での乱数を生成します。ただその分動作が遅いため、seedとしてたまに呼ぶ程度が良いと思われます。

C言語の場合（STLを使わない場合）

便利なSTLを一切使用せず、地道に実装する場合の方法です。 C言語やC++だけでなく、同様のアルゴリズムを実装することでどんな言語でも実現可能です。

シャッフルの手順

以下は要素の数がn個の配列をシャッフルする手順です：

配列の要素の中でランダムに１つ選ぶ
選んだ要素を1番目にする
配列の中のまだ選んでいない要素の中でランダムに１つ選ぶ
選んだ要素を2番目にする
以下すべて選ぶまで繰り返し

これで配列の要素を完全にランダムに並び替えることができます。

/* min_valからmax_val-1の範囲で整数の乱数を返す関数 */
int get_rand( int min_val, int max_val );

/* 要素数sizeの配列arrayの要素をシャッフルする関数 */
void shuffle( int* array, int size ) {
    for (int i = 0; i < size; i++) {
        int r = get_rand( i, size );
        int tmp = array[i];
        array[i] = array[r];
        array[r] = tmp;
    }
}