std::next_permutation通过字典序生成全排列，需先排序并循环调用直至返回false，可高效处理无重复或含重复元素的序列，适用于整数、字符串等可比较类型。
在C++中，std::next_permutation 是一个非常高效的算法工具，用于生成序列的下一个字典序排列。它定义在
工作原理简述
std::next_permutation 会重新排列当前序列，使其变为字典序中的下一个更大排列。如果当前已经是最大字典序（即完全降序），函数返回 false，并将序列重排为最小字典序（升序）；否则返回 true。
利用这一特性，只要从一个有序的初始序列开始（通常是升序），不断调用该函数，就能生成所有不重复的排列。
生成全排列的基本步骤
- 确保输入序列是可排序的容器（如 vector 或 array）
- 先对序列进行排序，得到字典序最小的排列
- 使用 do-while 循环输出当前排列并调用 next_permutation
- 循环直到 next_permutation 返回 false
示例代码：
立即学习“C++免费学习笔记（深入）”；
#include iostream>
#include
#include
using namespace std;
int main() {
vector
sort(nums.begin(), nums.end()); // 确保起始为最小排列
do {
for (int n : nums) cout cout } while (next_permutation(nums.begin(), nums.end()));
return 0;
}
使用技巧与注意事项
想要高效正确地使用 next_permutation 生成全排列，注意以下几点：
- 必须先排序：若初始状态不是最小字典序，会遗漏部分排列
- 支持任意可比较类型：不仅限于整数，字符串、自定义结构体（带比较运算符）也可用
- 自动去重：对于含重复元素的序列，它只会生成唯一的排列（前提是排序后调用）
- 时间复杂度合理：每个排列平均 O(n)，总复杂度 O(n! × n)，适合中小规模数据
例如处理重复元素：
vectorsort(s.begin(), s.end());
do {
cout } while (next_permutation(s.begin(), s.end()));
输出结果不会包含重复排列，系统自动跳过相同字典序的情况。
基本上就这些。掌握这个技巧后，写全排列问题可以简洁又高效，避免手动实现递归回溯的复杂逻辑。
