prev_permutation：不是“上一个排列”，而是“字典序严格更小的最近邻居”

你有没有试过，用 next_permutation 生成全排列后，突然想倒着查——比如当前是 "cba"，怎么快速拿到它前面那个合法排列 "cab"？别急着手写回溯或自己比大小，C++ 标准库早给你备好了 prev_permutation。但很多人用它时踩了坑：明明数组看着是降序，调用却返回 false；或者以为它“自动排序后取前一个”，结果逻辑全乱。今天我们就把它掰开揉碎，说清楚它到底在干什么、什么时候能用、以及为什么它比“先排序再反复调用”更可靠。

prev_permutation 的核心契约很简单：它只对当前序列执行一次“字典序意义上的前驱操作”，且仅当存在严格更小的排列时才成功修改并返回 true。注意两个关键词：“字典序”和“严格更小”。它不关心你数组是不是排好序的，也不保证调用后一定变成“最大可能的前一个”，它只做一件事：找到当前排列在所有全排列按字典序排好后的直接前驱——就像翻字典时，从“zebra”往前翻一页，停在“zeal”，而不是跳到“apple”。

举个具体例子。假设 vector<int> v = {2, 1, 3};，它的全部字典序排列是：
{1,2,3} → {1,3,2} → {2,1,3} → {2,3,1} → {3,1,2} → {3,2,1}
现在 v 是 {2,1,3}，调用 prev_permutation(v.begin(), v.end()) 后，v 变成 {1,3,2}，函数返回 true。再调一次？变成 {1,2,3}。第三次？返回 false，v 不变——因为 {1,2,3} 已经是字典序最小的排列，没有“更小”的邻居了。

这里藏着一个容易被忽略的事实：prev_permutation 的行为完全依赖于当前状态，而非初始顺序。也就是说，你不能假设“只要数组是降序，就一定能连调多次”。比如 v = {3,2,1}，第一次调用后变为 {3,1,2}（不是 {2,3,1}！），第二次是 {2,3,1}，第三次是 {2,1,3}……它走的是字典序链，不是数值大小链。有人曾误以为 {3,2,1} 调一次该变 {2,3,1}，那是把“数值递减”和“字典序前驱”混为一谈了。

实际使用中，最常出错的场景是：想生成“所有小于某目标排列”的排列，却没初始化到正确的起点。比如你想列出所有字典序小于 "dacb" 的 {'a','b','c','d'} 排列。正确做法是：先将容器设为 "dacb"，然后不断调用 prev_permutation 并收集结果，直到返回 false。错误做法是：先把容器排成 "abcd"，再幻想靠 prev_permutation 倒推——那根本不会触发，因为 "abcd" 是最小值，第一次就失败。

另一个实用技巧：它天然适合实现“撤销一步”式的枚举。比如你在解数独或填字游戏，每步生成一个候选排列，用户点了“上一步”，你不需要存整个历史栈，只需对当前状态调一次 prev_permutation 即可退回——前提是你的状态本身就是某个合法排列，且你明确知道它不是字典序最小的那个。

顺便提一句比较冷门但很实在的细节：prev_permutation 的时间复杂度是 O(n)，不是 O(n!)。它内部用的是经典的“找最长非升序后缀 + 查找交换 + 翻转”三步法，和 next_permutation 对称。这意味着哪怕你处理 100 个元素的排列（当然现实中几乎不会），单次调用依然飞快。只是要注意，它要求迭代器支持双向遍历（如 vector、deque 可以，list 行，forward_list 不行）。

最后划个重点：prev_permutation 不是万能倒带键。它只适用于已知当前状态是某个全排列，且你想沿字典序往回走一步的场景。如果你要的是“所有排列按降序输出”，正确姿势是：先 sort 升序，再用 do-while 配合 prev_permutation（注意初始状态得是最大排列，即 sort 后 reverse）；如果要“从某排列开始，向前生成 N 个”，那就循环调用，用计数器截断。

写完这段，我顺手测了下 vector<char>{'d','a','c','b'}：调一次变 'd','a','b','c'，再调是 'c','d','b','a'……没错，它真正在字典序里“翻页”，不是拍脑袋减一。工具本身很安静，但只有当你理解它翻的是哪本字典、哪一页，它才真正为你所用。