算法与数据结构 / permutation · 全部 n! 个排列的生成与编号 / 康托展开：给每个排列一个整数编号 待审核 4 / 4
rank / unrank · 阶乘进制

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

nn 个两两互异的元素，全部 n!n! 个排列按字典序排好后，每个都有唯一的名次，取值落在 00 到 n!−1n!-1 之间。康托展开 (Cantor expansion) 把这个名次和排列直接互算：rank 把排列映成序号，unrank 反向解码，无需像枚举那样一个个走。秘诀是把排列看成阶乘进制 (factorial number system) 下的数：第 ii 位的权重是 (n−1−i)!(n-1-i)!，该位的数位是「右边还没用、且比当前数小的个数」。

英文文献里这个排列到阶乘进制的映射通常叫 Lehmer code [2]，Cantor 1869 年那篇讲的是混合基数记数法本身 [3]；「康托展开」是中文竞赛社区的固定叫法。

1 · 序号到排列的解码

图 1-1 · unrank 的逐位解码。可拖动序号 kk，观察每一位如何按阶乘权重取出候选。

注 · 权重取阶乘的理由在于跨度。排列里第一位每变大一档（换成更大的可用数），就跨过了后面 (n−1)!(n-1)! 个排列，因为后面 n−1n-1 个位置能自由排出这么多种；第二位每变一档跨过 (n−2)!(n-2)! 个，依此类推。把「每位的档数 × 该位权重」加起来，正好是这个排列前面有多少个排列，也就是它的字典序名次。

警示 · 数位的取值范围逐位收窄。第 ii 位的数位只能落在 00 到 n−1−in-1-i 之间，最后一位永远是 00，因为只剩一个候选。这正是阶乘进制的特征：各位逢 2,3,4,…2, 3, 4, \dots 进一，而非十进制的逢十。

2 · 排列到序号的编码

rank 是 unrank 的逆。逐位扫描：第 ii 位的阶乘进制位是它右边比它小的个数（§1 的同一个量），乘以权重 (n−1−i)!(n-1-i)! 再累加。

图 2-1 · rank 的逐位编码。可编辑排列，观察每位如何数出右边比它小的个数并乘权重求和。

3 · 双射及其边界

rank 与 unrank 互为逆：对 n=1…6n = 1 \dots 6 全域枚举验证，rank(unrank(k)) 恒等于 kk。于是排列可以只用一个整数来存储、传输、比较——需要「字典序第 kk 个排列」时一步 unrank 即得，不必从最小一路 next 过去。前提是 k∈[0, n!)k \in [0,\, n!) 且元素两两互异。

警示 · 两条边界在实现里都没有防护。其一，越界的 kk 被静默接受：cantorUnrank(3, 6) 返回一个含空洞的数组而不抛错，cantorUnrank(3, -1) 同样。其二，元素重复时双射直接失效：[2,1,1] 的 rank 实测是 4，而它在多重集字典序里的真实名次是 2——权重仍按 n!n! 个位置算，重复元素把编号空间撑出了空洞。

警示 ·「只用一个整数」这句话有宽度上限。13!=6 227 020 80013! = 6\,227\,020\,800 越过 2^31 - 1，19!19! 越过 Number.MAX_SAFE_INTEGER。本页的 factorial 是 double 连乘，逐位与 BigInt 对照，第一个不精确的是 23!23!：返回 25852016738884978212864，真值是 25852016738884976640000，差 1572864。19!19! 到 22!22! 虽已超出安全整数但仍恰好精确，因为尾部 2 的因子足够多。n≥23n \ge 23 时这份实现不能再用来算 rank。

4 · 参考文献

  1. Knuth, D. E. (2011). The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1. Addison-Wesley. §7.2.1.2.
  2. Lehmer, D. H. (1960). Teaching combinatorial tricks to a computer. In Combinatorial Analysis (Proceedings of Symposia in Applied Mathematics, Vol. 10, pp. 179–193). American Mathematical Society.
  3. Cantor, G. (1869). Über die einfachen Zahlensysteme. Zeitschrift für Mathematik und Physik, 14, 121–128.