C++ STL中next_permutation函数如何实现排列的下一个排列顺序？

本文共计870个文字，预计阅读时间需要4分钟。

使用方法：+next_permutation(vt.begin(), vt.begin() + 3)+

参数：排序开始地址和排序结束地址的前三个元素

功能：对指定范围内的元素进行排序，并返回排序是否成功。

使用方法

参数

和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())); }