康拓展开式： 康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩，在组合数学中，其解决的是当前排列在全排列中的名次问题。简单来说，给定一个 n 位数的全排列，可根据康托展开公式确定其应是字典序中的第几个排列。由于康托展开计算的是某个全排列方式在该全排列集合中的字典序，其映射关系是唯一的，而且单调，因此映射关系是可逆的，故而当给定一个全排列的所有字符，以及某个字典序编号，可以利用逆康托展开得到相应的那个全排列。 总而言之就是求出该排列在全排列中排第几； 计算公式： 其中a[ i ] 表示的是原排列中其身后有多少个比它小的元素 代码如下：
void cantor(int str[],int n) { int ans=0; for(int i=0;i<n;i++) { int num=0; for(int j=i+1;j<n;j++) { if(str[i]>str[j]) num++;//计算其身后有多少个比它小的元素 } ans+=num*fun(n-i+1);//fun函数是计算阶乘的 } }逆康拖展开式： 如果已知 s = [“A”, “B”, “C”, “D”]，X(s1) = 20，能否推出 s1 = [“D”, “B”, “A”, “C”] 呢？ 因为已知 X(s1) = a43! + a32! + a21! + a10! = 20，所以问题变成由 20 能否唯一地映射出一组 a4、a3、a2、a1？如果不考虑 ai 的取值范围，有 33! + 12! + 01! + 00! = 20 23! + 42! + 01! + 00! = 20 13! + 72! + 01! + 00! = 20 03! + 102! + 01! + 00! = 20 03! + 02! + 201! + 00! = 20 等等。但是满足 0 <= ai <= n-1 的只有第一组。可以使用辗转相除的方法得到 ai，如下图所示：
已知值求其式子，用辗转相除法得到各个位上的值 知道了a4、a3、a2、a1的值，就可以知道s1[0] 是子数组[“A”, “B”, “C”, “D”]中第3大的元素 “D”，s1[1] 是子数组 [“A”, “B”, “C”] 中第1大的元素"B"，s1[2] 是子数组 [“A”, “C”] 中第0大的元素"A"，s[3] 是子数组 [“C”] 中第0大的元素"C"，所以s1 = [“D”, “B”, “A”, “C”]。
