C言語や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;
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としてたまに呼ぶ程度が良いと思われます。
余談ですが、乱数の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;
}
}
ここでget_rand()という範囲指定した乱数生成関数が必要となります。
具体的な実装方法については以下で解説しています。
単純に配列のサイズで剰余を取るのもいいですが、それでは偏りができてしまうため注意が必要です。
まとめ
C言語とC++それぞれでの配列（vector）のシャッフル方法を紹介しました。 こう見るとC++のSTLがいかに便利で強力かがよくわかりますね。 STLやC++11/14は偉大です。
余談
以下はC++11/14の機能を使ってより効率的なコードを書くために良い書籍です。基本的な入門というわけではなく、C/C++をある程度理解していることが必須です。
amazon.co.jpアルゴリズムやデータ構造はプログラミングをする上で基本的な知識です。スタック、キュー、ソーティングなど基本を網羅的に学べる書籍としてはこちらがおすすめです。
amazon.co.jp