算法与数据结构 / permutation · 全部 n! 个排列的生成与编号 待审核 4 页

permutation · 全部 n!n! 个排列的生成与编号

nn 个互异的数能排成 n!n! 种不同顺序。本系列从一个朴素的需求出发：给定一个排列, 不重不漏地走到「字典序里紧接着的下一个」, 进而枚举出全部排列；再换用回溯 (backtracking) 从空排列逐位生长出整棵选择树；最后用康托展开 (Cantor expansion) 把每个排列和一个整数序号 0…n!−10 \dots n!-1 一一对应起来。

每页都可单步播放：支点 (pivot) 与后继 (successor) 如何被找出、翻转 (reverse) 如何让后缀回到最小、递归如何「选 → 递归 → 撤销」地铺满选择树、序号如何在阶乘进制下被逐位解码成排列。主线是从局部一步的 next 到全局枚举, 再到回溯的递归视角与 rank / unrank 的编号双射。

生成：一个接一个, 再到一次全部

先把「下一个」这一步拆到原子级, 再看它如何驱动整体枚举, 以及回溯给出的另一种生成视角。

pivot + succ + reverse

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

从右找第一个上升沿作支点，在右段找大于它的最小者交换，再翻转后缀，即得字典序里紧接着的下一个排列。

 字典序枚举 · 反复调用 next

枚举全部：从最小走到最大

从升序出发反复调用「下一个排列」，直到抵达降序，恰好不重不漏地走遍全部 n!n! 个排列。

 回溯 · 选择树 · 选/递归/撤销

回溯生成：从空排列长出选择树

从空排列开始逐位选一个还没用过的数填进去，填满即得一个排列；试完一个分支就撤销去试别的，每片叶子正是一个完整排列。

编号：排列 ↔ 整数序号

排列不只是一堆顺序——它和区间 [0,n!)[0, n!) 里的整数是严格的一一对应。

rank / unrank · 阶乘进制

康托展开：给每个排列一个整数编号

把排列看成阶乘进制下的数，第 ii 位权重为 (n−1−i)!(n-1-i)!、数位是右边未用且更小的个数，rank 与 unrank 互为逆。

它真实跑在哪里

标准库：C++ std::next_permutation / prev_permutation、Python itertools.permutations 都在干这件事；前者正是本系列第一页的算法。 枚举与穷举：旅行商 (TSP) 的暴力解、座位 / 赛程 / 任务次序的全排列搜索、密码 / 组合的穷举, 都需要不重不漏地遍历排列。 字典序与排名：把排列编号存储 / 传输 (只存一个整数而非整个数组)、按字典序生成第 kk 个排列 (康托 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 的数学基础；英文文献里这个映射多称 Lehmer code。