順列生成とは
順列生成とは、複数の要素があるとき、その要素を並べる順番のパターンを全て生成することを意味する。
例えば {1, 2, 3} という要素列が有る場合、その全ての順列は以下のようになる。
{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}
上記を自分で生成するのは、結構難しいのだが、std::next_permutation または std::prev_permutation を使えば、上記を簡単に生成することが出来るぞ。
next_permutation
まずは、具体的な使い方から見てみよう。
#include <iostream>
#include <algorithm> // for next_permutation
#include <vector>
using namespace std;
int main() {
const int N = 3;
vector<int> v(N);
iota(v.begin(), v.end(), 1); // v に 1, 2, ... N を設定
do {
for(auto x : v) cout << x << " "; cout << "\n"; // v の要素を表示
} while( next_permutation(v.begin(), v.end()) ); // 次の順列を生成
return 0;
}
上記コードをビルド・実行すると、下図のようになる。
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
next_permutation() は配列またはコンテナクラスの範囲 [first, last) を引数で受け取り、その範囲の要素の次の順列を生成してくれる。
生成順序は、各順列が昇順になるように生成してくれる。※ 上記の各順列を3桁の数値とみなせば、各数値が昇順に並んでいるでしょ。
例えば、順列 {2, 1, 3} が与えられらた場合は、その次の順番の順列 {2, 3, 1} を生成する。
一番最後の順列 {3, 2, 1} が与えられた場合は、一番最初の順列 {1, 2, 4} を生成する。
next_permutation() は最後から最初の順列を生成した場合のみ false を返し、それ以外の場合は true を返す。
なので、最初に要素を昇順に並べておき、do - while ループで、next_permutation() がfalse を返すまでループすると、 全順列が生成されることになる。
なので、順列の数が予めわかっていれば、初期順列を一番最初のものにする必要は無い。
vector<int> v(3);
v[0], v[1], v[2] に異なる数値を設定
for(int i = 0; i < 6; ++i) { // 異なる数字３つの順列は６通りある
for(auto x : v) cout << x << " "; cout << "\n"; // v の要素を表示
next_permutation(v.begin(), v.end()); // 次の順列を生成
}
順列に同じ数字が入っている場合でも、next_permutation() は正しく動作してくれる。
vector<int> v{1, 2, 2}; // 要素が昇順に並んだ順列
do {
for(auto x : v) cout << x << " "; cout << "\n"; // v の要素を表示
} while( next_permutation(v.begin(), v.end()) ); // 次の順列を生成
上記を実行すると、下記のように出力される。
1 2 2 2 1 2 2 2 1
prev_permutation
prev_permutation と next_permutation の違い、順列を降順に並べた順序で、順列を生成する。 そして、降順に並べた最後から、最初の順序を生成した時点で false を返す。
したがって、初期順列は、要素を降順に並べておく。
vector<int> v{3, 2, 1}; // 要素が降順に並んだ順列
do {
for(auto x : v) cout << x << " "; cout << "\n"; // v の要素を表示
} while( prev_permutation(v.begin(), v.end()) ); // 前の順列を生成
上記を実行すると、下記のように出力される。
3 2 1 3 1 2 2 3 1 2 1 3 1 3 2 1 2 3
