简述
康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。设有n个数（1，2，3，4,…,n），可以有组成不同(n!种)的排列组合，康托展开表示的就是是当前排列组合在n个不同元素的全排列中的名次。
原理
X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!
其中, a[i]为整数，并且0 <= a[i] <= i, 0 <= i < n, 表示当前未出现的的元素中排第几个，这就是康托展开。
（PS：
康托展开表示的是当前排列在n个不同元素的全排列中的名次。比如213在这3个数所有排列中排第3。
那么，对于n个数的排列，康托展开为：
其中表示第i个元素在未出现的元素（即 第i位～第n位的数字中，也就是求后面有几个数字比ai小）中排列第几。举个简单的例子：
对于排列4213来说，4在4213中排第3（1234），注意从0开始，2在213中排第1（123），1在13中排第0（13），3在3中排第0（3），即：
，这样得到4213在所有排列中排第ans=3*3！+1*2！+0*1！+0*0！+1=20+1=21（20个小于的，所以排21）
）
例如有3个数（1，2，3），则其排列组合及其相应的康托展开值如下：
排列组合 名次 康托展开
123 1 0 * 2! + 0 * 1! + 0 * 0!
132 2 0 * 2! + 1 * 1! + 0 * 0!
213 3 1 * 2! + 0 * 1! + 0 * 0!
231 4 1 * 2! + 1 * 1! + 0 * 0!
312 5 2 * 2! + 0 * 1! + 0 * 0!
321 6 2 * 2! + 1 * 1! + 0 * 0!
比如其中的 231：想要计算排在它前面的排列组合数目（123，132，213），则可以转化为计算算比首位小及小于2的所有排列「1 * 2！」，首位相等及为2第二位小于3的所有排列「1*1！」，前两位相等及为23第三位小于1的所有排列（0*0！）的和即可，康托展开为：1*2！+1*1+0*0=3。
所以小于231的组合有3个，所以231的名次是4。
康托展开
再举个例子说明。
在（1，2，3，4，5）5个数的排列组合中，计算 34152的康托展开值。
首位是3，则小于3的数有两个，为1和2，a[5]=2，则首位小于3的所有排列组合为 a[0]*(5-1)!
第二位是4，则小于4的数有两个，为1和2，注意这里3并不能算，因为3已经在第一位，所以其实计算的是在第二位之后小于4的个数。因此a[4]=2
第三位是1，则在其之后小于1的数有0个，所以a[3]=0
第四位是5，则在其之后小于5的数有1个，为2，所以a[2]=1
最后一位就不用计算啦，因为在它之后已经没有数了，所以a[1]固定为0
根据公式：
X = 2 * 4! + 2 * 3! + 0 * 2! + 1 * 1! + 0 * 0!
= 2 * 24 + 2 * 6 + 1
= 61
所以比 34152 小的组合有61个，即34152是排第62。
具体代码实现如下：（假设排列数小于10个）
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 < n; ++i) {
int smaller = 0; // 在当前位之后小于其的个数
for (int j = i + 1; j < n; ++j) {
if (a[j] < a[i])
smaller++;
}
x += FAC[n - i - 1] * smaller; // 康托展开累加
}
return x; // 康托展开值
}
tips: 这里主要为了讲解康托展开的思路，实现的算法复杂度为O(n^2)，实际当n很大时，内层循环计算在当前位之后小于当前位的个数可以用 线段树来处理计算，而不用每次都遍历，这样复杂度可以降为O(nlogn)。
逆康托展开
一开始已经提过了，康托展开是一个全排列到一个自然数的双射，因此是可逆的。即对于上述例子，在（1，2，3，4，5）给出61可以算出起排列组合为 34152。由上述的计算过程可以容易的逆推回来，具体过程如下：
初始：1，2，3，4，5
用 61 / 4! = 2余13，说明a[5]=2,说明比首位小的数有2个，所以首位为3。
此时还剩1，2，4，5
用 13 / 3! = 2余1，说明a[4]=2，说明在第二位之后小于第二位的数有2个，所以第二位为4。此时：1，2，5
用 1 / 2! = 0余1，说明a[3]=0，说明在第三位之后没有小于第三位的数，所以第三位为1。此时：2，5
用 1 / 1! = 1余0，说明a[2]=1，说明在第二位之后小于第四位的数有1个，所以第四位为5。此时：2
最后一位自然就是剩下的数2啦。
通过以上分析，所求排列组合为 34152。
具体代码实现如下：（假设排列数小于10个）
b=[1]*(n)#预处理阶乘列表(为了方便空着下标为0的元素）
for i in range(2,n):
[i]=b[i-1]*i
def ff(n,num):#记得输入是大小和康托展开（康托展开=排名-1）！！！
nums=[]
i=n-1
flag=[1]*n#标记是否被使用
while i>0:
index=int(num/b[i])
num-=(index*b[i])
c=j=0
while c<index and j<n:#跳过前index个未使用的
if flag[j]==0:
j+=1
continue
j,c=j+1,c+1
#由于while循环的机制，此时c=index！！！！！
while flag[j]==0:#已经跳过足够个了，找出后面第一个未被使用的！
j+=1
flag[j]=0#标记已使用并放入nums中
nums.append(j+1)
i-=1
# 把最后一个剩下的加上
for j in range(n):
if flag[j]==1:
nums.append(j+1)