康托展开
原理：X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[1]*0! 0<=a[i]<i（1<=i<=n）
这就是康托展开的公式，其中a[i]为当前未出现的元素中是排在第几个（从0开始）。
应用：康托展开一般应用于寻找全排列数在其排列中的位置。例如{1,2,3}的全排列从小到大为123,132,213,231,312,321
我们假如要寻找312这个排列数在其序列中的位置，那么可以用康托展开。
首先我们来看第一个数，3，比3小的有1和2，即2*2！，第二个数为1，比1小的没有，故0*1！，第三个数为2，比2小的有1 ，而1已经在前面出现过了，故为0*0！加起来2*2！+0*1！+0*0！=4，即312前面有4个数，312排在第五个
注意，公式X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[1]*0! ，其中例子中n=3，a[3]=2,a[2]=0,a[1]=0。
| 排列组合 | 名次 | 康托展开 |
|---|---|---|
| 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! |
不需要检验某数码是否使用过，只需检查第(n+1-i)位之后比第(n+1-i)位小的位的数量，将这个数量作为公式中的a[i]。(1<=i<=n)
long int factory[] = { 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 count = 0;
for (int j = i + 1; j < n; j++)
{
if (a[j] < a[i])
count++;
}
x += count * factory[n - i - 1];
}
return x;
}逆康托展开
由康托展开可以得到排列数在其序列中位置，同样可以利用逆康托展开来求固定位置上的全排列数
例如在{1,2,3,4,5}的排列中，求第59个排列数：
排名从0开始，故59-1=58；
首先用58/4! ,得2余10，有2个比它小的数，故取3；
用余数10 / 3！，得1余4，有1个比它小的，故取2；
用4 / 2！，得2余0，有2个比它小的，而且2,3已经出现过，故取5；
用0 / 1！，得0，故取1；
最后一个即为4；
故排列数为32514。
/*
在由1到n组成的前n个数的全排列中，找字典序排第m的序列。
字典序最小的序列123...n，排名为0；
字典序最大的序列n...321，排名为(n!-1)。
如，在由1、2、3组成的序列的全排列中，
序列123的排名是0, 序列321的排名是5。
另外：代码中，facts[i]为i的阶乘；
*/
vector<int> decode(int n, int m){
vector<int> res;
long long board = 0;
int i, t, r;
/*
注意，如果需要的排名是[1, n]，
即在由1、2、3组成的序列的全排列中，要求序列123的排名是1，
那么，这里加一句：--m。
*/
for(t = n;t > 0;--t){
r = m / facts[t - 1];
m %= facts[t - 1];
for(i = 1;i <= n;++i){
if(!((board >> i) & 1)){
if(r == 0)break;
else --r;
}
}
res.push_back(i);
board |= 1 << i;
}
return res;
}