next_permutation是C++标准库中生成字典序下一个排列的函数，需先排序才能遍历全部不重复排列；它通过找降序后缀、交换、翻转实现，支持自定义比较但要求严格弱序。
next_permutation 是什么，它到底在做什么
next_permutation 是 C++ 标准库 vector 或数组）按字典序生成「下一个」排列。它不枚举全部，只负责从当前状态推进到字典序紧邻的下一个有效排列；如果当前已是最大排列（如降序），则返回 false 并将序列重置为最小排列（升序）。
它不是递归实现，也不分配额外空间，时间复杂度均摊 O(1)，最坏 O(n)，核心是「找最长后缀降序段 → 找后缀中首个大于前驱的元素 → 交换 + 翻转后缀」。
为什么直接用 next_permutation 前必须先排序
因为 next_permutation 只保证「字典序递增」，不保证从全排列集合的第一个开始。如果输入是乱序（如 {3,1,2}），调用一次 next_permutation 会跳到 {3,2,1}，直接漏掉 {1,2,3}、{1,3,2}、{2,1,3} 等前面所有排列。
- 正确做法：先用
sort(v.begin(), v.end())把容器排成升序（即字典序最小排列） - 然后在一个 do-while 循环里调用
next_permutation，确保覆盖全部 n! 种 - 错误写法：
while (next_permutation(...)) { ... }会漏掉初始状态
示例：
立即学习“C++免费学习笔记（深入）”；
vectorv = {3, 1, 2}; sort(v.begin(), v.end()); // → {1,2,3} do { // 处理 v } while (next_permutation(v.begin(), v.end())); // 共执行 6 次
next_permutation 对自定义类型或结构体怎么用
它依赖 operator，所以自定义类型必须提供可比较的严格弱序关系。不能只靠成员变量数量一致就认为可排列——缺少比较逻辑会导致行为未定义（可能无限循环或提前退出）。
- 确保类/结构体重载了
bool operator - 或者传入自定义比较函数对象：
next_permutation(it1, it2, comp) - 注意：比较函数必须满足严格弱序，禁止用
或随机逻辑 - 常见翻车点：结构体里有浮点字段，直接用
比较可能因精度导致排序不稳定
例如：
struct Point {
int x, y;
bool operator<(const Point& o) const {
return x != o.x ? x < o.x : y < o.y;
}
};
性能陷阱：重复元素时 next_permutation 还能用吗
能用，但结果不是「去重全排列」——next_permutation 本身不判重，它把相等元素也视为不同位置的独立个体。若输入含重复值（如 {1,1,2}），它仍会生成全部 3! = 6 个排列，其中 {1,1,2} 和 {1,1,2}（两 1 交换）被算作两个不同排列。
- 想得到真正去重的排列？必须先
sort，再用next_permutation，它内部已处理重复：当后缀中存在相同元素时，交换和翻转会自然跳过等价排列 - 验证方式：对
{1,1,2}排序后调用，实际只生成 3 个不同结果（{1,1,2},{1,2,1},{2,1,1}） - 但前提是容器已有序；如果乱序传入，重复逻辑失效，结果不可预测
真正容易被忽略的是：它的去重能力完全依赖于「输入已排序」+「元素可比较」这两个前提，缺一不可。
