気ままに実装する機械学習

機械学習に興味のある大学院生によるブログです. 機械学習以外のトピック多めです.

MENU

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. 配列を用いる場合

#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));
}

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

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

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

例えば、

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

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

1 5 3 
3 1 5 
3 5 1 
5 1 3 
5 3 1 

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

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()));
}

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

1 3 5 
1 5 3 
3 1 5 
3 5 1 
5 1 3 
5 3 1 

です.

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

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

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

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

まとめ

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

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

next_permutationは何かと便利ですね.