C++で順列生成 next_permutation - プログラミング初心者の勉強日記

競技プログラミングで順列を生成したくなることは良くあります.

例えば、グラフの最短経路問題のときに、訪れるべきノードが複数与えられていて、コストが最短になるような順番を求める問題の時、考えられる全順序を試してその最小を出力すればよくなります. (各ノード間の最短経路はワーシャルフロイドなどで解いていることを前提としています.)

訪れるべきノードが、「1, 3, 5」だとしたら、 $1 \rightarrow 3 \rightarrow 5$ , $1 \rightarrow 5 \rightarrow 3$ , $3 \rightarrow 1 \rightarrow 5$ , $3 \rightarrow 5 \rightarrow 1$ , $5 \rightarrow 1 \rightarrow 3$ , $5 \rightarrow 3 \rightarrow 5$ の全パターンを試せばよいことになります.

そんなときにC++ではnext_permutationを使います.

まず、順列の要素を配列や、vectorで与えてあげます.

ここでは、分けて説明することにします.

1. 配列を用いる場合
2. vectorの場合
まとめ

1. 配列を用いる場合

#include <iostream>
#include <algorithm>

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int array[3] = {1, 3, 5};
    do {
        rep(i, 0, 3) {
            cout << array[i] << " ";
        }
        cout << endl;
    } while(next_permutation(array, array + 3));
}

出力結果は以下のようになります.

int array[3] = {1, 3, 5};

で順列の要素を配列として与えています. このときに注意すべき点は、この配列は昇順にソートされていなければいけないという点です.

例えば、

int array[3] = {1, 5, 3};

というふうに定義した場合、出力結果は

と、意図した結果が得られなくなります.

next_permutation(array, array + 3)

では、配列の範囲を与えることで、その範囲の要素の次の順列を生成してくれます.

next_permutationでは、最後の順列を生成したあとに、最初の順列を生成しようとしたときにfalseを返すので、その時点でwhile文を抜けてくれます.

順列の要素の操作はdo-while文の中で行います. (例では単純に要素を先頭から出力しています.)

2. vectorの場合

#include <iostream>
#include <vector>
#include <algorithm>

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> v{1, 3, 5};
    do {
        rep(i, 0, 3) {
            cout << v[i] << " ";
        }
        cout << endl;
    } while(next_permutation(v.begin(), v.end()));
}

出力結果は配列のときと同じで、

です.

プログラムを見てもわかるとおり、配列のときとほぼ変わりません.

こちらも配列の時と同様、順列の要素を昇順にソートした状態でvectorに与えないといけないことに注意する必要があります.

next_permutation(v.begin(), v.end())

でコンテナクラスの範囲を指定しています. ここも配列のときとほぼ同じです.

まとめ

next_permutationをよく忘れるので自分用の防備録として記事にしました.

配列にしろ、vectorにしろソートしなければいけないことに注意が必要です.

next_permutationは何かと便利ですね.