[C++] [競プロ] next_permutationで順列を作る

競プロで順列に関する操作を行いたい時があります。例えば与えられた数字から作れる順列を列挙しろ、みたいな問題です。そんな時、C++ではnext_permutationという便利な関数があります。

使い方

まずは組み合わせの列挙をしたい配列を渡します。もちろん文字列でも可能です。今回は1,2,3の配列を渡してみます。

int main(void){
  vector<int> vec = {1,2,3};
  do {
    for(int i=0;i<vec.size(); i++) cout << vec[i];
    cout << endl;
  } while(next_permutation(vec.begin(), vec.end()));
  return 0;
}

// 結果

123
132
213
231
312
321

動作

next_permutationでは、与えられた配列を辞書順にソートした場合の次の要素で配列を置き換えてくれます。最初は {1,2,3} だった配列は1回目のnext_permutationで {1,3,2} 、次で {2,1,3} と順に置き換えられています。そして最後に {3,2,1} となった時、辞書順で次にくる要素がないためにnext_permutationは-1を返し、while文が終了します。 ちなみに、上記のコードでdo while文を使用しているのは最初の123を表示するためです。

注意点

上記のような動作原理となるため、全ての順列を列挙したい場合は昇順にソートした入力を与えないといけません。最初から {3,2,1} のような辞書順で最後(降順)の入力を渡すとそのまま終了します。

計算量

サイズNに対して順列はN!通りあります。よって、next_permutationの計算量も O(N!) となります。AtCoderの文脈で言うと、これは N<=10 までなら通用する範囲なので、それ以上の場合は全列挙以外のアプローチを考える必要があります。

next_permutationが使える例題

典型的な問題。

atcoder.jp