本文主要是介绍康拓展开（hash算法中会用到），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应）
公式：
X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!
其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）；
典型应用：
计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第几个。
应用实例
{1,2,3,4,...,n}表示1,2,3,...,n的排列如 {1,2,3} 按从小到大排列一共6个：123 132 213 231 312 321。他们间的对应关系可由康托展开来找到。
1324是{1,2,3,4}排列数中第几个大的数：
第一位是1小于1的数没有，是0个 0*3! ；
第二位是3小于3的数有1和2，但1已经在第一位了，即1未出现在前面的低位当中，所以只有一个数2 1*2! ；
第三位是2小于2的数是1，但1在第一位，即1未出现在前面的低位当中，所以有0个数 0*1! ；
所以比1324小的排列有0*3!+1*2!+0*1!=2个，1324是第三个大数。
下面是实现该功能的代码
#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define eps 1e-9
#define P system("pause")
using namespace std;
int n;
int fac[]={1,1,2,6,24,120,720,5040,40320,362880}; //假设排列的长度小于10
// 0!1!2!3! 4! 5! 6! 7! 8! 9!
int cantor(int *s)
{int sum=0,count;for(int i=0;i<n;i++){ count=0; for(int j=i+1;j<n;j++) if(s[i]>s[j]) count++;sum=sum+fac[n-i-1]*count; } return sum+1; //比当前排列小的有sum个，当前排列排在第sum+1位
}int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);int i,s[10];while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&s[i]);cout<<cantor(s)<<endl; } //P; return 0;
}
这篇关于康拓展开（hash算法中会用到）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
