std::prev_permutation 返回 false 且不修改序列，是因为当前序列已是字典序最小排列（如{1,2,3}），它仅生成前一个合法排列，不绕回最大排列。
std::prev_permutation 为什么返回 false 却没变出上一个排列
根本原因：它只对「当前序列的字典序前一个排列」有效，且要求输入序列本身是某个排列的「合法中间态」。如果当前序列已是字典序最小（如 {1,2,3}），调用 std::prev_permutation 不会修改容器，直接返回 false。
常见错误现象：
std::vector这不是 bug，是设计行为——它不负责“绕回”到最大排列（比如v = {1,2,3}; bool ok = std::prev_permutation(v.begin(), v.end()); // ok == false，v 仍是 {1,2,3}
{3,2,1}），那得你自己处理。
- 必须确保容器元素支持
比较，且已按升序/降序排好基础结构 - 若想枚举全部排列（含“绕回”），应先用
std::sort得到最大排列，再反复调用prev_permutation - 它修改的是原容器，不是返回新排列；别误以为它像 Python 的
itertools.permutations那样惰性生成
如何用 std::prev_permutation 枚举所有排列（从大到小）
关键步骤是「先排成最大字典序，再持续求前一个」。这和 next_permutation（从小到大）正好对称。
#include#include #include int main() { std::vector v = {1, 2, 3}; // 第一步：升序 → 最大排列需先降序 std::sort(v.begin(), v.end(), std::greater ()); do { for (int x : v) std::cout << x << ' '; std::cout << '\n'; } while (std::prev_permutation(v.begin(), v.end())); }
输出顺序是：3 2 1 → 3 1 2 → 2 3 1 → 2 1 3 → 1 3 2 → 1 2 3。注意最后一步后循环终止，prev_permutation 返回 false。
- 不能跳过
std::sort(..., std::greater)这步，否则起点不对，漏排列 - 循环条件必须是
while (prev_permutation(...))，不能写成do...while后再调一次——那样会多算一次失败状态 - 自定义比较器必须严格弱序；若用
std::greater，确保元素类型支持>
std::prev_permutation 和自定义类型配合要注意什么
核心是重载 operator 或传入二元谓词。它内部只做字典序比较，不关心语义。
立即学习“C++免费学习笔记（深入）”；
例如对结构体排序：
struct Point {
int x, y;
bool operator<(const Point& other) const {
return x != other.x ? x < other.x : y < other.y;
}
};
然后这样用：
std::vectorpts = {{2,1}, {1,3}, {1,2}}; std::sort(pts.begin(), pts.end()); // 先排成最大？不，先升序得到最小 // 若想从大到小枚举：先 std::sort(pts.rbegin(), pts.rend()) std::sort(pts.rbegin(), pts.rend()); // 等价于降序 do { // ... } while (std::prev_permutation(pts.begin(), pts.end()));
- 比较函数里不要有副作用（比如打印、修改全局变量）
- 如果用 lambda 作谓词，必须捕获为空，且声明为
constexpr（C++20 起）或确保可内联，否则某些标准库实现可能编译失败 - 浮点数慎用：因精度问题导致比较结果不稳定，
prev_permutation可能提前终止或死循环
性能与边界：为什么它比手写回溯快，但又不适合超长序列
时间复杂度是 O(n)，单次调用平均只扫描常数次；而生成全排列的总复杂度仍是 O(n! × n)，但它避免了递归栈开销和内存分配。
但实际使用中容易忽略两点：
- 它依赖当前排列的「邻接性」：两个相邻排列在字典序中只差常数位置交换，所以不能跳着走（比如想直接从第 100 个跳到第 50 个，不行）
- n > 12 时，
n!已超 4.7 亿，即使每次 O(1) 也撑不住；此时应考虑按需计算（如康托展开逆运算）而非枚举 - 没有内置去重逻辑：若容器含重复元素（如
{1,1,2}），prev_permutation仍会生成重复排列；要去重得先std::unique配合排序，或改用std::set缓存
真正难的从来不是调用这个函数，而是判断当前状态是否属于「可被 prev_permutation 处理的有效前驱」——它不报错，只沉默失败。
