康托展开与逆展开
康托展开
康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。设有n个数（1，2，3，4,…,n），可以有组成不同(n!种)的排列组合，康托展开表示的就是是当前排列组合在n个不同元素的全排列中的名次。
具体实现
对于n个数的全排列，共有n!中排列方式，如何求某一个序列在整个排列中的次序（从小到大）？
以9的全排列举例：842697513是1-9全排列的第几个？（高中数学排列组合问题，只需要做到不重不漏）
首先看第一位为8，那么第一位为1-7的全排列都比它小，共有7*8！个。
在第一位为8的情况下，其次看第二位为4，那么第二位为1-3的全排列都比它小，共有137！个。
在第一位为8，第二位为4的情况下，那么第三位为1的全排列都比它小，共有116！个。
在第一位为8，第二位为4，第三位为2的情况下，那么第四位为1-5的全排列都比它小，这里由于第二位4和第三位2已经确定，第四位的可能取值只能为（1,3,5），共有11135！
在第一位为8，第二位为4，第三位为2，第四位为6的情况下，那么第五位为1-8的全排列都比它小，这里由于第二位为4，第三位为2，第四位为6已经确定，第五位的可能取值只能为（1,3,5,7），共有11114*4！
……
对于第i位的可能取值，前i位的数字已经确定，且在全排列中每一个数字只能出现一次，只需要比较i位后面的数字比i位数字小的有几个，即可知道第i位的可能取值。
总结公式
X = a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!
其中X表示当前数列在所有全排列数中的是第X小(最小为0)
逆康托展开
由于康托展开是双向的，所以我们也可以对一个数进行逆康托展开。其意义是已知某一数列属于这个数列全排列中的第X小，求这个数列是什么。
对于数列(1,2,3,4,5),给出其康托展开为61,我们可以反向推出该数列。
用 61 / 4! = 2余13，说明a[5]=2,说明比首位小的数有2个，所以首位为3。
用 13 / 3! = 2余1，说明a[4]=2，说明在第二位之后小于第二位的数有2个，所以第二位为4。
- 用 1 / 2! = 0余1，说明a[3]=0，说明在第三位之后没有小于第三位的数，所以第三位为1。
- 用 1 / 1! = 1余0，说明a[2]=1，说明在第二位之后小于第四位的数有1个，所以第四位为5。
- 最后一位自然就是剩下的数2啦。
通过以上分析，所求排列组合为 34152。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
using namespace std;
const int N = 9; //数列长度
int fac[10] = {0,1,2,6,24,120,720,5040,40320,362880};
struct Mar
{
int mat[N];
};
int Contor(Mar res) //康托展开
{
int cnt,ans = 0;
for(int i=0;i<N;i++)
{
cnt = 0;
for(int j=i+1;j<N;j++)
{
if(res.mat[j] < res.mat[i]) cnt++;
}
ans += cnt * fac[N - i - 1];
}
return ans;
}
Mar deContor(int res) //为了紧凑而非常不优雅
{
Mar ans;
int i,j,k,pos = 0;
bool vis[10];
memset(vis,0,sizeof(vis));
for(i=N;i>1;i--) //循环n-1次
{
k = res / fac[i-1];
res = res % fac[i-1];
for(j=1;k>=0;j++)
if(!vis[j]) k--;
ans.mat[pos++] = --j;
vis[j] = 1;
}
for(j=1;vis[j];j++);
ans.mat[pos] = j;
return ans;
}
int main()
{
int kase;
cin >> kase;
while(kase--)
{
Mar a,b;
for(int i=0;i<N;i++) cin >> a.mat[i];
int c = Contor(a);
cout << "The Cantor is " << endl;
cout << c << endl;;
b = deContor(c);
cout << "The deCantor is" << endl;
for(int i=0;i<N;i++) cout << b.mat[i] << ' ';
cout << endl;
}
}