【筆記】常用C++ algorithm:next_permutation

  • is_permutation:判斷陣列 b 是否為陣列 a 排序後的結果。
    • is_permutation(a, a+5, b);
  • next_permutation:使用已經排序(由小到大)的資料,產生下一組排列。
  • prev_permutation:針對已經「逆向」排序(由大到小)的資料,產生上一組排序。

【範例】ZeroJudge e446: 排列生成

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    int a[5] = {9, 3, 1, 7, 5};
    int b[5] = {1, 3, 5, 7, 9};
 
    //判斷陣列 b 是否為陣列 a 排序後的結果
    cout << is_permutation(a, a+5, b) << "\n";
 
    cout << "產生下一組排列" << "\n";
    string s = "bca";
    sort(s.begin(), s.end());
    do {
        cout << s << "\n";
    } while (next_permutation(s.begin(), s.end()));
    
    cout << "產生上一組排列" << "\n";
    s = "bca";
    sort(s.begin(), s.end(), greater<char>());
    do {
        cout << s << "\n";
    } while (prev_permutation(s.begin(), s.end()));
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> v;
    for (int i = 1; i <= N; i++){
        v.push_back(i);
    }
    for (auto i:v){
        cout << i << " ";
    }
    cout << "\n";
    while (next_permutation(v.begin(), v.end())){
        for (auto i:v){
            cout << i << " ";
        }
        cout << "\n";
    }
    return 0;
}
分享本文 Share with friends