【算法笔记】康托展开

介绍

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

公式

$X=a_n(n-1)!+a_{n-1}(n-2)!+\cdots+a_1\cdot0!$
其中, $a_{i}$ 为整数,并且 $0\leq a_{i}<i,1\leq i\leq n$ 。
$a_{i}$ 的意义参见举例中的解释部分

解释

因为排列是按字典序排名的，因此越靠前的数字优先级越高。也就是说如果两个排列的某一位之前的数字都相同，那么如果这一位如果不相同，就按这一位排序。

举例

例如，$3~5~7~4~1~2~9~6~8$ 展开为 $98884$。因为$X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884$.

解释：

排列的第一位是3，比3小的数有两个，以这样的数开始的排列有8!个，因此第一项为2*8!

排列的第二位是5，比5小的数有1、2、3、4，由于3已经出现，因此共有3个比5小的数，这样的排列有7!个，因此第二项为3*7!

以此类推，直至0*0!

用途

显然，$n$位$(0 \sim n-1)$全排列后，其康托展开唯一且最大约为$n!$，因此可以由更小的空间来储存这些排列。由公式可将$X$逆推出唯一的一个排列。

康托展开的逆运算

既然康托展开是一个双射，那么一定可以通过康托展开值求出原排列，即可以求出n的全排列中第x大排列。

如 $n=5,x=96$ 时：

首先用 $96-1$ 得到 $95$ ，说明 $x$ 之前有 $95$ 个排列.(将此数本身减去 $1$ ) 用 $95$ 去除 $4!$ 得到 $3$ 余$23$，说明有3个数比第 $1$ 位小，所以第一位是 $4$. 用 $23$ 去除 $3!$ 得到 $3$ 余 $5$ ，说明有3个数比第 $2$ 位小，所以是 $4$ ，但是 $4$ 已出现过，因此是 $5$. 用 $5$ 去除 $2!$ 得到 $2$ 余 $1$ ，类似地，这一位是 $3$. 用 $1$ 去除 $1!$ 得到 $1$ 余 $0$ ，这一位是 $2$. 最后一位只能是 $1$. 所以这个数是 $45321$.

按以上方法可以得出通用的算法。

优化

树状数组

我们在处理 $a_i$ 时，要每次统计小于当前一位数且没有被选过的数字个数，复杂度为 $\Theta (n^2)$ .
考虑使用树状数组，建树时均赋值为 $1$ ，被选中后 $add(1, n, -1)$ 即可。
时间复杂度为 $\Theta (n \log n)$