permutation · 把全部 n！个排列玩通透
n 个互异的数能排成 n! 种不同顺序。本系列从一个朴素的需求出发: 给定一个排列, 不重不漏地走到「字典序里紧接着的下一个」, 进而枚举出全部排列; 再换用回溯 (backtracking) 从空排列逐位生长出整棵选择树; 最后用康托展开 (Cantor expansion) 把每个排列和一个整数序号 0 … n!−1 一一对应起来。
每页都是可单步播放的 demo: 看支点 (pivot) 与后继 (successor) 如何被找出、翻转 (reverse) 如何让后缀回到最小、递归如何「选 → 递归 → 撤销」地铺满选择树、序号如何在阶乘进制下被逐位解码成排列。一条主线: 局部一步 (next) → 全局枚举 (enumerate) → 递归视角 (backtrack) → 编号双射 (rank/unrank)。
生成: 一个接一个, 再到一次全部
先把「下一个」这一步拆到原子级, 再看它如何驱动整体枚举, 以及回溯给出的另一种生成视角。
下一个排列：让顺序「刚好大一点」
字典序里紧接着的下一个排列怎么求？从右找第一个上升沿（支点 pivot），在它右边的递减段里找大于支点的最小者（后继 succ），交换两者，再翻转支点之后的后缀使其回到最小。单步看四个动作如何精确拼出「下一个」；整段递减时则回环到最小排列。
枚举全部：从最小一路走到最大
从升序（最小排列）出发，反复调用「下一个排列」，直到抵达降序（最大排列），恰好不重不漏地走遍全部 n! 个。单步观察清单按字典序逐行点亮，留意每一步用到的支点位置在哪——它解释了相邻两个排列差在哪几位。
回溯生成：从空排列长出选择树
换一个视角：从空排列开始，逐位选一个还没用过的数填进去，填满即得一个排列；试完一个分支就撤销（回溯） 去试别的。单步沿递归树深度优先地展开，看「选 → 递归 → 撤销」如何系统地铺满全部叶子——每片叶子正是一个完整排列。
编号: 排列 ↔ 整数序号
排列不只是一堆顺序 —— 它和区间 [0, n!) 里的整数是严格的一一对应。
康托展开：给每个排列一个整数编号
把排列看成阶乘进制 (factorial number system) 下的一个数：第 i 位的权重是 (n-1-i)!，数位则是「右边还没用、且比当前数小的个数」。于是 rank 把排列映成序号 0 … n!-1, unrank 反向解码。单步看序号如何逐位还原成排列——排列与整数严格一一对应。
它真实跑在哪里
std::next_permutation / prev_permutation、Python itertools.permutations 都在干这件事; 前者正是本系列第一页的算法。
枚举与穷举: 旅行商 (TSP) 的暴力解、座位 / 赛程 / 任务次序的全排列搜索、密码 / 组合的穷举, 都需要不重不漏地遍历排列。
字典序与排名: 把排列编号存储 / 传输 (只存一个整数而非整个数组)、按字典序生成第 k 个排列 (康托 unrank)、判断两个排列谁在前。
回溯框架: 排列是回溯法最经典的入门模型, N 皇后、数独、子集 / 组合枚举都共用「选 → 递归 → 撤销」这套骨架。相关链接
- 双指针 · two pointers 本站 · sequence 系列 「下一个排列」里翻转后缀用的就是对撞双指针; 找支点 / 后继也是从右向左的线性扫描 —— 同属序列扫描技巧。
- 搜索与回溯 · backtracking 本站 · search 系列 回溯生成排列是该范式的入门模型; 同样的「选 → 递归 → 撤销」骨架支撑起 N 皇后、子集枚举与约束求解。
- Permutation — Generation in lexicographic order en.wikipedia.org Narayana Pandita (14 世纪) 给出的字典序下一个排列算法, 即本系列第一页四步法的来源与正确性说明。
- Factorial number system (factoradic) en.wikipedia.org 阶乘进制的定义与「factoradic ↔ 排列」的双射, 即康托展开 rank / unrank 的数学基础。