C++でFisher-Yatesアルゴリズムを実装し配列をランダムにシャッフルする方法

Fisher-Yatesアルゴリズムは、配列の要素に対してランダムな順列を生成するアルゴリズムです。すなわち、配列内の全要素をランダムにシャッフルします。このアルゴリズムは偏り（バイアス）を持たないため、考えられるすべての順列が等しい確率で現れるという特徴があります。

以下は、C++でFisher-Yatesアルゴリズムを実装し、配列をシャッフルするプログラム例です。

C++での実装例

#include <iostream>
#include <cstdlib>
using namespace std;
int main() {
   int n;
   cout << "配列のサイズを入力してください: "<<endl;
   cin >> n;

   int arr[n], arr1[n], index_arr[n];
   int index;
   cout << "配列の要素を入力してください: "<<endl;
   for (int i = 0; i < n; i++)
   cin >> arr[i];
   for (int i = 0; i < n; i++)
   index_arr[i] = 0;
   for (int i = 0; i < n; i++) {
      do {
         index = rand() % n;
      }
      while (index_arr[index] != 0);
      index_arr[index] = 1;
      arr1[i] = arr[index];
   }
   cout<<"シャッフル後の配列: ";

   for (int i = 0; i < n; i++)
   cout << arr1[i] << " ";
   return 0;
}

実行結果

上記プログラムの実行結果は以下の通りです。

配列のサイズを入力してください: 10
配列の要素を入力してください: 1 2 3 4 5 6 7 8 9 10
シャッフル後の配列: 4 7 8 6 3 10 2 1 9 5

プログラムの流れと解説

まず、ユーザーから配列のサイズと各要素を入力として受け取ります。該当するコードは以下の部分です。

cout << "配列のサイズを入力してください: "<<endl;
cin >> n;

int arr[n], arr1[n], index_arr[n];
int index;

cout << "配列の要素を入力してください: "<<endl;

for (int i = 0; i < n; i++)
cin >> arr[i];

配列の入力が完了したら、使用済みインデックスを管理するためのindex_arr[]をすべて0で初期化します。その後、rand()関数を使って0からn-1までのランダムなインデックスを生成し、まだ使用されていないインデックス（index_arr[index]が0の状態）が選ばれるまで再抽選を繰り返します。選ばれたインデックスには1を設定して使用済みとマークし、対応する要素を新しい配列arr1[]へ格納していきます。これにより、同じ要素が重複して選ばれることなく、すべての要素がちょうど一度ずつ配置されます。

for (int i = 0; i < n; i++) {
do {
   index = rand() % n;
}
while (index_arr[index] != 0);
index_arr[index] = 1;
arr1[i] = arr[index];
}

最後に、シャッフルされた配列を画面に表示して処理を終了します。

cout<<"シャッフル後の配列: ";

for (int i = 0; i < n; i++)
cout << arr1[i] << " ";

補足：実行ごとに異なる結果を得るには

上記のコードではrand()をそのまま使用しているため、プログラムを実行するたびに同じシャッフル結果になります。実行ごとに異なる結果を得たい場合は、main関数の冒頭でsrand(time(NULL))を呼び出して乱数シードを初期化してください（その際は<ctime>のインクルードが必要です）。

また、この実装は「未使用のインデックスが出るまで再抽選する」方式のため、最悪計算量はO(n²)となります。要素数が非常に多い配列を扱う場合は、末尾から順にランダムな位置の要素と交換していく古典的なFisher-Yatesシャッフル（Knuthシャッフル）の方がO(n)で効率的なので、用途に応じて使い分けるとよいでしょう。