このエントリーをはてなブックマークに追加

順列生成 next_permutation, prev_permutation 入門
Copyright (C) 2015 by Nobuhide Tsuda

 

※ イラスト提供:かわいいフリー素材集「いらすとや」様

順列生成とは

順列生成とは、複数の要素があるとき、その要素を並べる順番のパターンを全て生成することを意味する。

例えば {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) {   // 異なる数字3つの順列は6通りある
        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

まとめ・参考