STLのprev_permutationをC++で実装する方法

STL（標準テンプレートライブラリ）の prev_permutation は、範囲 [first, last] 内の要素を、辞書順でひとつ前の順列に並べ替えるための関数です。順列とは、N個の要素が取りうる N! 通りの並び方のうちの1つを指します。この記事では、STLの prev_permutation を使ったC++プログラムの実装方法を解説します。

アルゴリズム

処理の流れは以下のとおりです。

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

まず配列を降順にソートしておくことで、辞書順で最大の順列から開始し、prev_permutation によって順に小さな順列を生成できる点がポイントです。

サンプルコード

#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<<"Enter number of elements to be inserted: ";
    cin>>e;
    int elements[e];
    for (i = 0; i < e; i++) {
        cout<<"Enter "<<i + 1<<" element: ";
        cin>>elements[i];
    }
    sort (elements, elements + e);
    reverse (elements, elements + e);
    cout << "The "<<e<<"! possible permutations with ";
    cout<<e<<" elements: "<<endl;
    do {
        show(elements, e);
    }
    while (prev_permutation(elements, elements + e));
    return 0;
}

実行結果

Enter number of elements to be inserted: 4
Enter 1 element: 7
Enter 2 element: 6
Enter 3 element: 10
Enter 4 element: 2
The 4! possible permutations with 4 elements:
10 7 6 2
10 7 2 6
10 6 7 2
10 6 2 7
10 2 7 6
10 2 6 7
7 10 6 2
7 10 2 6
7 6 10 2
7 6 2 10
7 2 10 6
7 2 6 10
6 10 7 2
6 10 2 7
6 7 10 2
6 7 2 10
6 2 10 7
6 2 7 10
2 10 7 6
2 10 6 7
2 7 10 6
2 7 6 10
2 6 10 7
2 6 7 10

補足：prev_permutationの動作について

prev_permutation は、現在の並びを辞書順でひとつ前の順列に変換します。すでに最初の（最小の）順列である場合は、最後の（最大の）順列に戻り、false を返します。そのため、do-while文と組み合わせることで、すべての順列を網羅的に出力できます。

なお、サンプルコードでは可変長配列（VLA）を使用していますが、これはC++の標準規格では保証されていません。移植性を高めたい場合は、std::vector<int> の使用を検討してください。