康托展开公式：
把一个整数X展开成如下形式：
X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!
其中，a为整数，并且0<=a[i]<i(1<=i<=n)
应用：
{1,2,3,4,...,n}表示1,2,3,...,n的排列
如 {1,2,3} 按从小到大排列一共6个。分别是是s1{1, 2, 3} s2{1, 3, 2} s3{2, 1,,3}
s4{2, 3, 1} s5{3, 1, 2} s6{3, 2, 1} 。
康托展开就是要把10进制数与与其中的排列一一对应起来。
那么s3{2, 1,
3}的康托展开式是什么呢。因为{1,2,3}有三个数字,所有n = 3,则s2的可以用康托展开式表示为：
X(s3) = a3 * (2)! + a2 * (1)! + a1 * (0)!;
只要求出a3,a2,a1即可，就是s2中对应数字在排列{1,2,3}中是第几个小的数，也就是出数字本身比它数还小的个数。
2在{2, 1, 3}比它小的只有数字1，所以a3 = 1，
1在{1, 3}比它小的数字没有，所以a2 = 0，(2已经计算)，
3在{3}比它小的数字也没有，所以a1 = 0。(1,2，已经计算过)
所以：X(s3) = 1 * (2)! + 0 * (1)! + 0 * (0)! = 2;
依次可得：
X(s1) = 0 * (2)! + 0 * (1)! + 0 * (0)! = 0;
X(s1) = 0 * (2)! + 0 * (1)! + 0 * (0)! = 0;
X(s2) = 0 * (2)! + 1 * (1)! + 0 * (0)! = 1;
X(s3) = 1 * (2)! + 0 * (1)! + 0 * (0)! = 2;
X(s4) = 1 * (2)! + 1 * (1)! + 0 * (0)! = 3;
X(s5) = 2 * (2)! + 0 * (1)! + 0 * (0)! = 4;
X(s6) = 2 * (2)! + 1 * (1)! + 0 * (0)! = 5;
知道了X康托展开通过辗转相除法就可以求出对应排列，
比如：X(s5) = 4。
则a3 = 4 / (2)! = 2, 余数为0，
a2 = 0 / (1)! = 0, 余数为0,
a1 = 0 / (0)! = 0, 余数为0。
通过康托展开就可以得到全排列。
康托展开代码:
1 #define ll long long 2 ll fac[]={1,1,2,6,24,120,720,5040,40320,362880};//阶乘表 3 ll cantor(int s[], int n) 4 { 5 int i, j, t; 6 ll result = 0; 7 for (i = 0; i < n - 1; i++)//最后一个可以不用计算 8 { 9 t = 0;//比s[i]小的个数 10 for (j = i + 1; j < n; j++) 11 if (s[i] > s[j]) 12 t++; 13 result += t * fac[n - i -1]; 14 } 15 return result; 16 }
康托逆展开代码:
1 ll cantorInverse(ll result, int s[], int n) 2 { 3 int i; 4 for (i = n - 1; i >= 0; i--) 5 { 6 s[i] = result / fac[i]; 7 result %= fac[i]; 8 } 9 }