全排列与 康托展开

对于没有重复元素的全排列来说，存在如下的对应关系

X=an(n-1)!+an-1(n-2)!+...+ai(i-1)!+...+a21!+a1*0!

ai为整数，并且0<=ai<i(1<=i<=n)

这种对应称为康托展开，是一种全排列与整数的双射，n位（0~n-1）全排列后，其康托展开唯一且最大约为n!

可用于压缩状态，可作为Hash函数。

康托展开：

int contor(int num[]){
	int k=1;
	for(int i=1;i<=n;i++){
		int t=0;
		for(int j=i+1;j<=n;j++){
			if(num[i]>num[j]){
				t++;
			}
			
		}k+=t*fac[n-i];
	}
	return k;
}

康拓逆展开：

void recontor(int num[],int k){
	int t=0;k--;
	bool f[12]={0};
	for(int i=1;i<=n;i++){
		t=k/fac[n-i];
		int j;
		for( j=1;j<=n;j++){
			if(!f[j]){
				if(t<=0) break;
				t--;
			}
		}
		num[i]=j;
		f[j]=1;
		k%=fac[n-i];
	}
}