算法与数据结构 / permutation · 全部 n! 个排列的生成与编号 / 枚举全部：从最小走到最大 待审核 2 / 4
字典序枚举 · 反复调用 next

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

有了「下一个排列」这一步，枚举全体几乎不费力气：从升序（字典序最小）出发反复调用 next，每次跳到紧邻的下一个，直到抵达降序（字典序最大）。nn 个元素两两互异时，整条路径恰好不重不漏地覆盖全部 n!n! 个排列。

1 · 不重不漏的理由

字典序在这 n!n! 个互异排列上是一个严格全序：任意两个都可比，且没有并列。「下一个排列」给出的是严格大于当前、且没有任何排列夹在中间的那一个。于是从最小反复取下一个，就像沿数轴一格格走，既不会跳过谁，也不会回头重复，走到最大时正好遍历完 n!n! 个。

图 1-1 · 从最小排列反复求下一个，直到抵达降序，恰好走遍全部 n!n! 个排列。可切换 nn，或用「直接跳到最大」按钮观察每一步用到的支点位置。

警示 · 元素有重复时这个计数不成立。nextPermutation 的比较写作 a[i] >= a[i+1] 与 a[j] <= a[i]，对重复元素本身是正确的——它生成的是多重集排列，共 n!/∏mi!n! / \prod m_i! 个。实测 [1,1,2] 反复调用只有三个：112 → 121 → 211，而非 3!=63! = 6。本页与康托展开的所有计数都以元素互异为前提。

2 · 标准库里的同一条序列

Python 的 itertools.permutations(range(1, n+1)) 与 C++ 里「sort 后反复 next_permutation 直到返回 false」产出的正是这条字典序序列 [1]。需要按序处理全部排列（枚举所有座位、赛程、路径次序）时，「最小 → 反复 next → 最大」是最省心的写法。

警示 · 阶乘增长极快，10!=3 628 80010! = 3\,628\,800，而 13!=6 227 020 80013! = 6\,227\,020\,800 已经越过 2^31 - 1，从这个规模起就要挑数据类型。逐个枚举只适合很小的 nn；当 nn 稍大、又只需要「第 kk 个」或「某排列的编号」时，用康托展开在 O(n2)O(n^2) 内直接换算。生成视角的另一面是回溯，同一批排列换成递归树来铺。

3 · 参考文献

  1. ISO/IEC. Programming languages — C++, [alg.permutation.generators].