介绍
康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。
公式
\(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)\)
