【C++】配列の内容をシャッフルするアルゴリズム（Fisher-Yates法）

このアルゴリズムは、与えられた配列の内容をシャッフルし、要素のランダムな順列を生成します。この手法は「Fisher-Yatesシャッフル（フィッシャー・イェーツのシャッフル）」として広く知られており、すべての順列が等しい確率で現れることが保証された効率的な方法です。

解き方のポイントは、配列の末尾のインデックスから開始し、0からそのインデックスまでの範囲でランダムに選んだ位置の要素と入れ替えていくことです。これにより、計算量O(n)で配列全体をシャッフルできます。

入力と出力

入力：
整数の配列：{1, 2, 3, 4, 5, 6, 7, 8}

出力：
シャッフル後の配列：3 4 7 2 6 1 5 8（※実行するたびに結果は異なります）

アルゴリズムの手順

randomArr(array, n)

入力： 配列と要素数

出力： シャッフルされた配列

Begin
    for i := n - 1 down to 1, do
        j := random number from 0 to i
        swap arr[i] and arr[j]
    done
End

処理の流れ

1. i を n-1 から 1 まで減らしながら繰り返します。
2. 各ループで、0 から i の範囲の乱数 j を生成します。
3. arr[i] と arr[j] の内容を入れ替えます。

C++による実装例

#include <iostream>
#include<cstdlib>
#include <ctime>
using namespace std;

void display(int array[], int n) {
    for (int i = 0; i < n; i++)
        cout << array[i] << " ";
}

void randomArr ( int arr[], int n ) {   // ランダムな配列要素を生成
    srand (time(NULL));                 // 時刻を使って異なるシード値を設定
    for (int i = n-1; i > 0; i--) {
        int j = rand() % (i+1);         // 0からiの中からランダムにインデックスを選択
        swap(arr[i], arr[j]);           // 現在の要素とj番目の要素を入れ替え
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = 8;
    randomArr(arr, n);
    display(arr, n);
}

実行結果

4 7 8 2 6 3 5 1

まとめ

このシャッフルアルゴリズムは、配列の要素数をnとすると時間計算量O(n)、空間計算量O(1)で動作する非常に効率的な手法です。srand(time(NULL))によって実行ごとに異なるシード値を設定することで、毎回異なるシャッフル結果が得られる点も重要なポイントです。