【C++】next_permutation（順列列挙）

AtCoder Beginner Contest 150のC問題で出てきたnext_permutationの使い方を確認

C - Count Order

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)

int main(){
   int n; 
   cin >> n;
   vector<int>p(n),q(n);
   rep(i,n)cin >> p[i];
   rep(i,n)cin >> q[i];
   vector<int>a(n);
   rep(i,n) a[i] = i+1;

   map<vector<int>,int>mp;
   do{
       mp[a] = mp.size();
   }while(next_permutation(a.begin(),a.end()));
   
   int ans = abs(mp[p] - mp[q]);
   cout << ans << endl;
   return 0;
}

・next_permutationを使うと全ての順列を列挙することができる

※全ての順列を取得する場合は、関数に最初に与える範囲が昇順にソート済みになっている必要がある

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;

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

（実行結果）

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

・元の配列の要素で作ることができる最後の順列を作った時だけ（上の例なら4321）falseを返し、それ以外はtrueを返してくれるのでwhileでの繰り返しに使える

仕組みとしてはnext_permutationが1回呼ばれるごとに対象の配列を昇順に次の順列へ並び替えている

int main() {
   vector<int> v = {1, 2, 3, 4};
   for(auto p:v) cout << p;
   next_permutation(v.begin(), v.end());
   cout << endl;
   for(auto p:v) cout << p;
   return 0;
}

（実行結果）

1234
1243