【组合数学】康托展开 学习笔记

康托展开

将 $1…n$ 的所有排列按照字典序进行排序，某个排列的排名可以通过康托展开的方法求出。

观察排列 $2,3,1,4$ 和 $2,3,4,1$，发现第一个不同的位置是第三位，而且第一个排列的第三位比第二个小，根据字典序的性质，第一个排列的排名在第二个之前。

从这里我们也可以发现判断某个排列排名之前的排列数量的方法。对于 $2,3,4,1$ 这个排列，我们逐位分析：

• 第一位：$2$，我们根据分类加法计数原理对所有排列进行分类：
  • 如果一个排列的第一位是 $1$，则后面三位可以任意排列，有 $3!$ 种情况。
  • 如果一个排列的第一位是 $3,4$，显然后面如何排列都不满足条件。
  • 如果一个排列的第一位是 $2$，分为下一类。
• 第二位：$3$，我们再对第一位是 $2$ 的排列进行分类：
  • 第二位是 $1$，后面的两个数可以任意排列，有 $2!$ 种情况。
  • 第二位是 $4$，显然后面如何排列都不满足条件。
  • 第二位是 $3$，分为下一类。
• 第三位：$4$：我们对前两位是 $2,3$ 的排列进行分类：
  • 第三位是 $1$ 对答案产生 $1!$ 的贡献。
  • 第三位是 $4$ 则是排列 $2,3,4,1$ 本身。

所以，最终的答案就是 $13! + 12! + 1*1! = 9$，有 $9$ 个排列的字典序比这个排列小，所以这个排列的排名是 $10$。

由此可得比某排列的字典序小的排列数量：
$$\sum_{i=1}^{n}(c_{a[i]} \times (n-i)!)$$

其中，$c_{a[i]}=\sum_{j=i}^n [a[j]<a[i]]$，表示第 $i$ 个数后面比 $a[i]$ 小的数，可以用树状数组计算，见 【数据结构】树状数组 学习笔记。把所有字典序比给定排列小的排列按 $i$ 进行分类，$(c_{a[i]} \times (n-i)!)$ 表示排列的前 $i-1$ 项和给定排列完全相同时，字典序小的排列的数目。这样分类是不重不漏的，因此求和便得到答案。

参考代码：

代码模板-康托展开

逆康托展开

由排名反推原排列，这就是逆康托展开要解决的问题。它与康托展开互为逆运算，本质上是分类加法计数原理的逆向使用——我们已知被“跳过”的排列总数，现在要反推出每一位具体是什么数字。

我们继续沿用排列 $2,3,4,1$（$n=4$）这个例子。已知它的排名是 $10$，即比它小的排列有 $9$ 个（记 $k=9$）。现在我们手里只有 $k=9$，要还原出 $2,3,4,1$，依然采用逐位分析：

• 第一位：对于 $1,2,3,4$ 这 $4$ 个数，以每个数字开头的排列各有 $3! = 6$ 种。

  • 我们用 $k = 9$ 除以 $3!$，得到商 $1$，余数 $3$。
  • 这个商 $1$ 表示：第一位被跳过了 1 个数字（即数字 $1$ 开头的所有 $6$ 种情况），所以第一位应该是初始数字中的第 $2$ 小，即 $2$。选定第一位后，令 $k$ 更新为余数 $3$。
  • 后续分析只需在剩余数字 ${1,3,4}$ 中进行

• 第二位：固定第一位后，在剩余数字中，以某个数作为第二位的排列各有 $2! = 2$ 种。

  • 用 $k = 3$ 除以 $2!$，得到商 $1$，余数 $1$。
  • 商 $1$ 表示第二位的选择跳过了 $1$ 个数字（即跳过最小的数字 $1$），所以第二位应取剩余数字中的第 $2$ 小，即 $3$。更新 $k = 1$。
  • 后续分析只需在剩余数字 ${1,4}$ 中进行

• 第三位：在剩余数字 ${1,4}$ 中，固定第三位后，第四位只有 $1! = 1$ 种排法。

  • 用 $k = 1$ 除以 $1!$，得到商 $1$，余数 $0$。
  • 商 $1$ 表示第三位的选择跳过了 $1$ 个数字（即跳过最小的数字 $1$），所以第三位取剩余数字中的第 $2$ 小，即 $4$。更新 $k = 0$。

• 第四位：此时只剩数字 $1$，且 $k=0$ ，所以应当取用 $1$，还原完毕，得到排列 $2,3,4,1$。

由此，我们可以总结出逆康托展开的通用的递推步骤：

1. 给定排名，求得 $k$（即“比它小的排列个数”）。
2. 维护一个有序的剩余数字集合 $S$（初始为 $1, 2, …, n$）。
3. 从第 $1$ 位到第 $n$ 位依次确定：
   • 计算当前剩余数字的排列数，即 $(n-i)!$。
   • 计算 权重 $t = \left\lfloor \dfrac{k}{(n-i)!} \right\rfloor$。
   • 在有序集合 $S$ 中，选取第 $t+1$ 小的数字作为当前位的 $a[i]$，因为 $t$ 表示跳过了 $t$ 个比它小的数字），所以排列的排名（比他小的排列的个数）会增加 $t*(n-i)!$。
   • 若选择更大（小）的数字，则以此为前缀的任意排列的字典序都比最早要求的 $k$ 更小（大）。
   • 从 $S$ 中移除 $a[i]$。
   • 更新 $k = k \bmod (n-i)!$（即余数留给后续位使用）。

这个步骤本质上是在反复做带余除法：每一位的商 $t$ 指明了该位在剩余可选数字中的“偏移量”，而余数则传递给下一位继续分解。最终，$k$ 会被分解为唯一的阶乘数系表示（即阶乘进制），而这个进制表示恰好对应着原排列的每一位选择。

在算法实现中，维护动态有序集合 $S$ 并快速查询第 $t+1$ 小元素，通常可以使用线段树二分、树状数组倍增或平衡树来完成，从而在 $O(n \log n)$ 的时间内还原出完整的排列。

参考代码：还没写。

参考资料 && 推荐题目

1. 置换和排列 - OI Wiki