康托展开

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

原理介绍康托展开运算

其中, 为整数,并且 。

表示原数的第i位在当前未出现的元素中是排在第几个

z康托展开的逆运算

既然康托展开是一个双射，那么一定可以通过康托展开值求出原排列，即可以求出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。

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

康托展开和逆康托展开康托展开举例再举个例子说明。
在5个数的排列组合中，计算 34152的康托展开值。

首位是3，则小于3的数有两个，为1和2，，则首位小于3的所有排列组合为

第二位是4，则小于4的数有两个，为1和2，注意这里3并不能算，因为3已经在第一位，所以其实计算的是在第二位之后小于4的个数。因此。

第三位是1，则在其之后小于1的数有0个，所以。

第四位是5，则在其之后小于5的数有1个，为2，所以。

最后一位就不用计算啦，因为在它之后已经没有数了，所以固定为0

根据公式：

所以比34152小的组合有61个，即34152是排第62。

代码实现static const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; // 阶乘int cantor(int *a, int n){ int x = 0; for (int i = 0; i