C++でSTLを使用して配列のすべての逆順列を生成する方法

この記事では、C++のSTL（Standard Template Library）を使用して、配列のすべての逆順列を生成する方法を解説します。たとえば、(1, 2, 3) という数値列の順方向の順列と逆順列は、それぞれ以下のようになります。

順方向の順列

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

逆順列

3, 2, 1
3, 1, 2
2, 3, 1
2, 1, 3
1, 3, 2
1, 2, 3

逆順列を求めるには、STLの prev_permutation() 関数を使用します。この関数は、現在の並びを辞書式順序で1つ前の順列に変換し、前の順列が存在すれば true を、存在しなければ false を返します。

アルゴリズム

getPermutation(arr, n)

Begin
    配列 arr をソートする
    配列 arr を逆順に反転する
    繰り返す
        配列の要素を出力する
    prev_permutation の計算が完了するまで
End

サンプルコード

#include<iostream>
#include <algorithm>
using namespace std;
void disp(int arr[], int n){
    for(int i = 0; i<n; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}
void getPermutation(int arr[], int n) {
    sort(arr, arr + n);
    reverse(arr, arr+n);
    cout << "Possible permutations: \n";
    do{
        disp(arr, n);
    }while(prev_permutation(arr, arr+n));
}
int main() {
    int arr[] = {11, 22, 33, 44};
    int n = sizeof(arr) / sizeof(arr[0]);
    getPermutation(arr, n);
}

コードの解説

• sort()：まず配列を昇順にソートします。
• reverse()：ソート済みの配列を逆順（降順）に反転します。これにより、辞書式順序で最大の並びから順列の生成を開始できます。
• prev_permutation()：do-whileループ内で呼び出され、現在の並びを1つ前の順列に変換します。これ以上前の順列が存在しない場合（最小の並びになった場合）には false を返し、ループが終了します。

出力結果

Possible permutations:
44 33 22 11
44 33 11 22
44 22 33 11
44 22 11 33
44 11 33 22
44 11 22 33
33 44 22 11
33 44 11 22
33 22 44 11
33 22 11 44
33 11 44 22
33 11 22 44
22 44 33 11
22 44 11 33
22 33 44 11
22 33 11 44
22 11 44 33
22 11 33 44
11 44 33 22
11 44 22 33
11 33 44 22
11 33 22 44
11 22 44 33
11 22 33 44