C++でstd::vectorをシャッフルする方法（Fisher-Yatesアルゴリズム）

std::vectorの要素をシャッフルするには、古典的なFisher-Yatesシャッフルアルゴリズムを利用する方法があります。

このアルゴリズムでは、ベクターを先頭から線形に走査し、各要素を「その要素自身を含む残りの要素」の中からランダムに選ばれた要素と入れ替えていきます。これにより、すべての並び順が等しい確率で現れる、偏りのないシャッフルが実現できます。

アルゴリズム

Begin
  show()関数を宣言する。
    show()関数内で、ベクターのconst参照を引数として受け取る。
    for (auto const& i : input)
      変数iの値を出力する。
  vector型の変数vを宣言する。
    配列形式でvに初期値を設定する。
  整数型の変数sizeを宣言する。
    size()関数を呼び出してベクターのサイズを取得する。
    size = v.size() を代入する。
  for (int i = 0; i < size - 1; i++)
    int j = i + rand() % (size - i)
    swap()関数を呼び出して、v[i]とv[j]の値を入れ替える。
  「シャッフル後の要素」を出力する。
  show()関数を呼び出して、シャッフル後のvの内容を表示する。
End.

サンプルコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void show(vector<int> const &input) {
    for (auto const& i : input) {
        std::cout << i << " ";
    }
}

int main() {
    vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int size = v.size();

    for (int i = 0; i < size - 1; i++) {
        int j = i + rand() % (size - i);
        swap(v[i], v[j]);
    }

    cout << "シャッフル後の要素" << endl;
    show(v);
    return 0;
}

実行結果

シャッフル後の要素
2 8 5 3 1 9 4 7 6

※乱数を使用しているため、実行するたびに表示される要素の順序は変わります。

補足：C++11以降ならstd::shuffleが便利

rand()は乱数の品質が低く、分布に偏りが生じる可能性があります。実務では、<random>ヘッダーで提供される乱数エンジンとstd::shuffleを組み合わせる方法が推奨されます。

#include <random>
#include <algorithm>

std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(v.begin(), v.end(), gen);

std::shuffleは内部でFisher-Yatesアルゴリズムを採用しており、高品質な乱数で確実にシャッフルできます。特別な理由がない限り、こちらの利用を検討するとよいでしょう。