1.简单介绍
康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。
比如，在所有包含 的全排列中，我们定义以下的双射：
康托展开的实质是计算当前排列在所有由小到大全排列中的顺序。 由上图可知序列 最小，序列 最大。
康托展开的公式为：
代表比当前排列小的排列的个数，因此最终我们需要的答案就是 ，其中 表示当前排列里从位置 右侧算起，比位置 的数还要小的数的个数，注意 从左到右依次为 。
举个例子：求 的康托展开。首位是1，1的右边比1小的数没有，所以 ，注意这里是 而不是 。同理有：
，，， 所以最终有：
所以 在所有包含 的升序全排列中排在第24位！！！
2.代码实现
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
//先预先算好0~9的阶乘，方便计算
int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};
//x=a[n]*(n-1)! a[n-1]*(n-2)! ... a[1]*0!，注意i是从1~n，没有0
int Contor(char *a,int n) {
int sum=0,small=0;
for(int i=0;i<n;i ) {
small=0;
for(int j=i 1;j<n;j ) {
if(a[j]<a[i]) { //计算第i位右边比该数还要小的数的个数
small ;
}
}
sum =small*fac[n-i-1];
//例如12345，i=0时实际上对应着5
//顺数第i位实际上对应着第n-i位 ，即a[n-i]=small,所以应该是small* ((n-i)-1)!
//所以应该是small*fac[n-i-1]
}
return sum 1;
}
int main() {
int n,t;
char a[10];
cin>>n>>a;
cout<<Contor(a,n);
return 0;
}
