定义：

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

公式：

$X=a_n(n-1)!+a_{n-1}(n-2)!+\ldots+a_1\cdot0! + 1$

其中，$a_i$为整数，并且$0\le a_i \le i,1\le i \le n.$

用途：

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

举例：

对于一个有n个不同元素的集合${1,2,3,4,\dots,n}$的从小到大排序（从大到小 同理）的全排列 显然它有$n！$项。如n=4，那么就有$4！=4×3×2×1=24$项。

与自然数$1，2，3，4，\dots n！$与之一一对应。比如 $1～4$四个数的全排列按字典序如下：

问：求4132是第几个排列？

解：总共4个数，所以n=4.ans:=0;

1. 第一个数是4，研究比4小的并且还没有出现过的数有3个：1，2，3。

   其中，a4 = 3 ，那么ans:=ans+3*(n-1)!所以 ans:= ans+ 3*(4-1)! =18

2. 第二个数是1，研究比1小的并且还没有出现过的数为 0个。

   其中，a3 = 0 ，那么ans:=ans+0 * (n-2)!，那么ans不变。

3. 第三个数是3，研究比3小的并且还没有出现过的数为1个：1，2。

   其中，a2 = 2 ，那么ans:=ans+ 1* (n-3)!,那么ans:=18+1* (4-3)!=19

4. 第四个数是2，研究比2小的并且还没有出现过的数为0个。

   其中，a1 = 0 ，那么ans不变。

最后ans怎么等于19啊？？代表它前面有19个排列嘛，那么4132自己就是第20个罗（ 最后ans:=ans+1）

逆展开：

**例：**1～5从小到大全排列中，找出第96个排列？

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

总结 + 代码：

int fac[] = {1,1,2,6,24,120,720,5040,40320}; //阶乘

//康托展开
int kt(int n,int s[]){ 
    int sum = 0,smallNum;
    for(int i=0; i < n; i++){
        smallNum = 0; //比当前数小的数
        for(int j=i+1; j<n; j++)
            if(s[i] > s[j]) smallNum++;
        sum += smallNum * fac[n-i-1];
    }
    return sum;
}
//康托逆展开
void invKT(int n, int k, int s[]){
    int t,j;
    bool visit[10] = {false}; //需要记录该数是否已在前面出现过
    for(int i=0; i<n; i++){
        t = k/fac[n-i-1];
        for(j=1; j<=n; j++){
            if(!visit[j]){
                if(t == 0) break;
                t--;
            }
        }
        s[i] = j;
        visit[j] = true;
        k %= fac[n-i-1];
    }
}