pivot + succ + reverse

下一个排列：让顺序刚好大一点

把一个排列看成一串数字，按从左到右的优先级比大小，就有了它们的字典序 (lexicographic order)。给定其中一个，如何走到紧接着的下一个——既要变大，又要变得尽量少？答案是三次扫描加一次交换：从右找支点、在右段找后继、交换、翻转后缀。本页把这几步拆到原子级。以下均设 $n$ 个元素两两互异。

结果可以再次作为输入，从而枚举全部排列（见枚举全部）；若想直接拿到「第 $k$ 个」而非一个个走，见康托展开。

1 · 支点的位置

一个排列的后缀若是递减的（如 $\dots, 5, 4, 1$ ），它已经是这几位能排出的最大顺序，在不动前面的前提下没法再变大。所以必须往左退到第一个能抬一下的位置：第一个满足 $a_i < a_{i+1}$ 的 $i$ ，这就是支点 (pivot)。抬高它、再把它后面压到最小，整体就恰好大了一档。

图 1-1 · 下一个排列的四个原子动作：找支点、找后继、交换、翻转后缀。可切换预设排列，或用「用结果继续」按钮把输出再喂回输入。

2 · 四个动作的分工

注 · 每一步各自负责一件事。找支点定位「哪一位需要进位」；找后继 (succ) 取右段里大于支点的最小者（右段递减，从右数第一个就是最小的那个），用它替换支点能让前缀只增大最少的量；交换后右段仍然递减；翻转把右段从最大翻成最小。合起来即：前缀进位最小、后缀取最小。

警示 · 整段递减时没有支点。像 5 4 3 2 1 已是字典序最大，找不到上升沿， $i$ 退到 $-1$ 。按循环约定，它的下一个回到最小排列 1 2 3 4 5，直接翻转整段即可。C++ 的 std::next_permutation 在这种情况下返回 false，同时也把序列变回升序。

3 · 代价

三次扫描各不超过一趟，交换是 $O(1)$ ，全程就地修改、不需额外空间，所以单次调用的最坏代价是 $O(n)$ 。

注 · 摊还代价与 $n$ 无关，这一点值得单独量一下。给实现插桩后枚举全体： $n = 4$ 时每次调用平均 3.043 次比较、1.478 次交换； $n = 6$ 是 3.075 与 1.540； $n = 8$ 与 $n = 9$ 都稳定在 3.077 与 1.543。支点扫描的期望长度是一个收敛级数，与 $n$ 无关，所以枚举全体的算法开销是 $\Theta(n!)$ 而非 $\Theta(n \cdot n!)$ ——后者只在把每个排列都拷出来时才成立。C++ 标准对 next_permutation 的保证是每次调用至多 $\lfloor n/2 \rfloor$ 次交换 [2]，与实测的 1.543 对照，正是「最坏 $O(n)$ 、摊还 $O(1)$ 」。

4 · 参考文献

Knuth, D. E. (2011). The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1. Addison-Wesley. §7.2.1.2, Algorithm L.
ISO/IEC. Programming languages — C++, [alg.permutation.generators].