康托展开可以用来求一个 (1sim n) 的任意排列的排名。
什么是排列的排名？
把 (1sim n) 的所有排列按字典序排序，这个排列的位次就是它的排名。
时间复杂度？
康托展开可以在 (O(n^2)) 的复杂度内求出一个排列的排名，在用到树状数组优化时可以做到 (O(nlog n)) 。
怎么实现？
因为排列是按字典序排名的，因此越靠前的数字优先级越高。也就是说如果两个排列的某一位之前的数字都相同，那么如果这一位如果不相同，就按这一位排序。
比如 (4) 的排列， ([2,3,1,4]<[2,3,4,1]) ，因为在第 (3) 位出现不同，则 ([2,3,1,4]) 的排名在 ([2,3,4,1]) 前面。
举个栗子
我们知道长为 (5) 的排列 ([2,5,3,4,1]) 大于以 (1) 为第一位的任何排列，以 (1) 为第一位的 (5) 的排列有 (4!) 种。这是非常好理解的。但是我们对第二位的 (5) 而言，它大于 第一位与这个排列相同的，而这一位比 (5) 小的 所有排列。不过我们要注意的是，这一位不仅要比 (5) 小，还要满足没有在当前排列的前面出现过，不然统计就重复了。因此这一位为 (1,3) 或 (4) ，第一位为 (2) 的所有排列都比它要小，数量为 (3 imes 3!) 。
按照这样统计下去，答案就是 (1+4!+3 imes 3!+2!+1=46) 。注意我们统计的是排名，因此最前面要 (+1) 。
注意到我们每次要用到 当前有多少个小于它的数还没有出现 ，这里用树状数组统计比它小的数出现过的次数就可以了。
原理总结：
- 注意到我们每次要用到 当前有多少个小于它的数还没有出现
- 这里用树状数组统计比它小的数出现过的次数就可以了，可以优化到
O(nlogn)
代码
先预处理阶乘：
void init(){
fact[0] = 1;
for(int i = 2;i <= 9; ++i) fact[i] = fact[i - 1] * i;
//递推求阶乘
}
//或者直接打表
int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
(cantor) 函数
int cantor(int a[],int n){
int ans = 0;
for(int i = 0;i < n; ++i){
int cnt = 0;
for(int j = i + ;j < n; ++j)++cnt;
// 找到a[i]是当前数列中未出现的数中第几小的
// 从1开始，即1-n的全排列
// 从0开始，就变成了0-n的全排列，记得变通
ans += cnt * fact[n - i - 1];
}
return ans + 1;//如果输出的是排名就要 + 1，如果是hash值可以直接返回 ans
}
逆康托展开
而逆康托展开相当于，反过来操作
因为排列的排名和排列是一一对应的，所以康托展开满足双射关系，是可逆的。可以通过类似上面的过程倒推回来。
如果我们知道一个排列的排名，就可以推出这个排列。因为 (4!) 是严格大于 (3 imes 3!+2 imes 2!+1 imes 1!) 的，所以可以认为对于长度为 (5) 的排列，排名 (x) 除以 (4!) 向下取整就是有多少个数小于这个排列的第一位。
引用上面展开的例子
首先让 (46-1=45) ， (45) 代表着有多少个排列比这个排列小。 (lfloorfrac {45}{4!} floor=1) ，有一个数小于它，所以第一位是 (2) 。
此时让排名减去 (1 imes 4!) 得到 (21) ， (lfloorfrac {21}{3!} floor=3) ，有 (3) 个数小于它，去掉已经存在的 (2) ，这一位是 (5) 。
(21-3 imes 3!=3) ， (lfloorfrac {3}{2!} floor=1) ，有一个数小于它，那么这一位就是 (3) 。
让 (3-1 imes 2!=1) ，有一个数小于它，这一位是剩下来的第二位， (4) ，剩下一位就是 (1) 。即 ([2,5,3,4,1]) 。
实际上我们得到了形如 有两个数小于它 这一结论，就知道它是当前第 (3) 个没有被选上的数，这里也可以用线段树维护，时间复杂度为 (O(nlog n)) 。
代码
vector<int> incantor(int x,int n){
x--;//得到从0开始的排名
vector<int> res(n); //保存数列答案
int cnt;
bool st[10]; //标记数组
memset(st,false,sizeof st);
for(int i = 0;i < n; ++i){
cnt = x / fact[n - i - 1]; // 比a[i]小且没有出现过的数的个数
x %= fact[n - i - 1]; //更新 x
for(int j = 1; j <= n; ++j){// 找到a[i]，从1开始向后找
if(st[j]) continue; // 如果被标记过，就跳过
if(!cnt){ // 如果cnt == 0说明当前数是a[i]
st[j] = 1; //标记
res[i] = j; // 第i位是j
break;
}
cnt--; // 如果当前不是0，就继续往后找
}
}
return res;// 返回答案
}