【C++】next_permutation(順列列挙)
AtCoder Beginner Contest 150のC問題で出てきたnext_permutationの使い方を確認
#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
よろしければサポートお願いします! いただいたサポートはクリエイターとしての活動費に使わせていただいております!