競プロで順列に関する操作を行いたい時があります。例えば与えられた数字から作れる順列を列挙しろ、みたいな問題です。そんな時、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が使える例題
典型的な問題。
