引入：
对于一个1~n的排列，如果我们要想将它作为状态保存起来，一般都会开一个大小为n^n的n维数组，但这样的话经常会爆空间复杂度，但又想到1~n的排列最多只有n！个，远小于n^n，故考虑用一个数代表一个排列，压缩空间。康托展开，就是将一个排列对应成它在全排列中的序数，即这个排列在所有排列中从小到大排第几。（当然也可以从大到小排）
如何求一个排列的康托展开？
有一个公式：rank=a1(n−1)!+a2(n−2)!+?+an?0!，其中rank为当前排列x1，x2，...，xn的康托展开值，ai为xi后面的，即xi+1~xn中小于xi的数的个数。
（解释挖坑）
1 int cantor(int x[],int n) 2 {//cantor展开,n表示是n位的全排列，x[]表示全排列的数（用数组表示） 3 int ans=0,sum=0; 4 for(int i=1;i<n;i++){ 5 for(int j=i+1;j<=n;j++) 6 if(x[j]<x[i]) 7 sum++;//记录后面有多少个比xi小的 8 ans+=sum*factorial[n-i];//累积 factorial为预处理好的阶乘值 9 sum=0;//计数器归零 10 } 11 return ans+1;//+1是因为序数要算上自己。如果是求它前面有多少个排列，则不用加 12 }
例题：
典型运用康托展开压缩状态
扩展：逆康托展开（挖坑）
原文：https://www.cnblogs.com/InductiveSorting-QYF/p/12679235.html