c++中如何使用std::prev_permutation生成上一个排列_c++算法技巧【实例】_技术教程

std::prev_permutation 返回 false 且不修改序列，是因为当前序列已是字典序最小排列（如{1,2,3}），它仅生成前一个合法排列，不绕回最大排列。

std::prev_permutation 为什么返回 false 却没变出上一个排列

根本原因：它只对「当前序列的字典序前一个排列」有效，且要求输入序列本身是某个排列的「合法中间态」。如果当前序列已是字典序最小（如 {1,2,3}），调用 std::prev_permutation 不会修改容器，直接返回 false。

常见错误现象：

std::vector v = {1,2,3};
bool ok = std::prev_permutation(v.begin(), v.end()); // ok == false，v 仍是 {1,2,3}

这不是 bug，是设计行为——它不负责“绕回”到最大排列（比如 {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 或传入二元谓词。它内部只做字典序比较，不关心语义。

例如对结构体排序：

struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        return x != other.x ? x < other.x : y < other.y;
    }
};

然后这样用：

std::vector pts = {{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 处理的有效前驱」——它不报错，只沉默失败。