C++ STL中 next_permutation 函数的用法

使用方法

参数

和sort的参数一样，一般传两个参数，第一个是排列开始的地址，第二个是排列结束的下一个地址，如实现数组前三位的下一个排列：next_permutation(vt.begin(), vt.begin() + 3), 一般作用对象是数组和字符串

作用

next_permutation是求当前排列的下一个排列（按字典序升序的下一个序列）, 如1234的next_permutation是1243 prev_permutation是求当前排列的上一个排列，如4321的prev_permutation是4312

返回值

返回值是true或者false，若当前排列有下一个排列，则返回true，反之返回false：如54321的返回值为false。该函数会直接修改数组为下一个排列。

示例1: 输出{1, 2, 3}的全排列

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

int main() {
    vector<int> vt = {2, 1, 3};
    sort(vt.begin(), vt.end());  // 先要升序排序, 转换为{1, 2, 3}
    do {
        for (int i = 0; i < vt.size(); i++) {
            cout << vt[i] << " ";
        }
        cout << endl;
    } while (next_permutation(vt.begin(), vt.end()));
    
    cout << endl;
    for (int i = 0; i < vt.size(); i++) {
        cout << vt[i] << " ";   // 经过一轮循环, 恰好又回到初值: {1, 2, 3}
    }
}

/*
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2
3 2 1

1 2 3
*/

当然, 也可以使用prev_permutation函数

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

bool cmp(int a, int b) {
    return a > b;
}

int main() {
    vector<int> vt = {2, 1, 3};
    sort(vt.begin(), vt.end(), cmp);  // 先要降序排序, 转换为{3, 2, 1}
    do {
        for (int i = 0; i < vt.size(); i++) {
            cout << vt[i] << " ";
        }
        cout << endl;
    } while (prev_permutation(vt.begin(), vt.end()));
    
    cout << endl;
    for (int i = 0; i < vt.size(); i++) {
        cout << vt[i] << " ";   // 经过一轮循环, 恰好又回到初值: {3, 2, 1}
    }
}

/*
3 2 1 
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3

3 2 1
*/

示例2: 输出字符串"abc"的全排列

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

int main() {
    string str = "bac";
    sort(str.begin(), str.end());  // 先要升序排序, 转换为"abc"
    do {
        for (int i = 0; i < str.size(); i++) {
            cout << str[i] << " ";
        }
        cout << endl;
    } while (next_permutation(str.begin(), str.end()));
}

/*
a b c 
a c b
b a c
b c a
c a b
c b a
*/

示例3: 求数组的第n个全排列

举例说明: 4个数的集合为 {1, 2, 3, 4}, 要求出最后一个即第n = 24个排列

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

int main() {
    string num = "1234";
    int n = 1;  // 注意n从1开始❗

    do {
        if (n == 24) {
            for (int i = 0; i < num.size(); i++) {
                cout << num[i];  // 4321
            }
            break;
        }
        n++;

    } while (next_permutation(num.begin(), num.end()));
}