STLのnext_permutationを使って順列を生成するC++プログラム

next_permutationとは

STL（標準テンプレートライブラリ）のnext_permutationは、範囲[first, last]内の要素を、辞書順で次に大きな順列へと並べ替えるための関数です。順列とは、N個の要素が取り得るN!通りの並べ方のうちの1つを指します。この記事では、STLのnext_permutationを利用して、すべての順列を生成・表示するC++プログラムを紹介します。

アルゴリズム

Begin
    整数型の配列変数 elements[] を定義する。
    データの個数 e をユーザーから入力してもらう。
    キーボードから入力された e 個のデータで配列 elements[] を初期化する。
    配列の全要素をソートする。
    do
        show(elements, e)  // 配列の現在の内容を表示する
    while (next_permutation(elements, elements + e))
End

サンプルコード

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

void show(int a[], int n) {
    for(int i = 0; i < n; i++) {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

int main () {
    int e, i;
    cout<<"挿入する要素の個数を入力してください: ";
    cin>>e;
    int elements[e];
    for (i = 0; i < e; i++) {
        cout<<i + 1<<" 番目の要素を入力してください: ";
        cin>>elements[i];
    }
    sort (elements, elements + e);
    cout << e <<" 個の要素による "<<e<<! 通りの順列: "<<endl;
    do {
        show(elements, e);
    }
    while (next_permutation(elements, elements + e));
    return 0;
}

実行結果

挿入する要素の個数を入力してください: 4
1 番目の要素を入力してください: 7
2 番目の要素を入力してください: 6
3 番目の要素を入力してください: 2
4 番目の要素を入力してください: 10
4 個の要素による 4! 通りの順列:
2 6 7 10
2 6 10 7
2 7 6 10
2 7 10 6
2 10 6 7
2 10 7 6
6 2 7 10
6 2 10 7
6 7 2 10
6 7 10 2
6 10 2 7
6 10 7 2
7 2 6 10
7 2 10 6
7 6 2 10
7 6 10 2
7 10 2 6
7 10 6 2
10 2 6 7
10 2 7 6
10 6 2 7
10 6 7 2
10 7 2 6
10 7 6 2

解説のポイント

• next_permutationは、現在の並びを基準として次の順列を作り、成功すればtrue、それ以上の順列が存在しなければfalseを返します。
• 最初にsortで昇順に並べておくことで、最小の順列（辞書順で最初の並び）からスタートし、最後まですべての順列を漏れなく生成できます。
• すべての順列を出力し終えると、配列は再び昇順ソートされた状態に戻ります。

注意点

サンプルコード中のint elements[e]のような可変長配列（VLA）はGCCなどのコンパイラ固有の拡張機能です。標準C++に厳密に準拠したい場合は、std::vector<int>の使用を推奨します。また、要素数が増えると順列の総数は階乗（N!）で爆発的に増加するため、実用的には要素数は10程度までにとどめるのが安全です。