参考博客:https://blog.csdn.net/Hi_KER/article/details/81263889 

康托展开解决的两个问题:

  • 正康托展开:给出一个全排列的序列,求该序列是第几个全排列的序列。

           如初始序列1234,那么3214是第15个全排列的序列

  • 逆康托展开:给出数字k,求全排列序列中的第k个序列是什么。

           如初始序列1234,第15个全排列的序列为3214

康托展开是为了解决全排列和序号之间的映射问题,对于全排列,可以通过next_permutation(a,a+n)(或者pre_permutation(a,a+n))去求解,当然也可以自己写一个递归回溯函数求解。

 

正康托展开


给定n=4,序列:3214,求该排列字典序?

第一位为3,则当第一位为1,2时生成的排列比目标排列小,有所以2*3!种;

第二位为2,当第二位为1是生成的排列更小,有1*2!种;

第三位为1,没有比1更小的排列方法,有0*1!种

第四位为4,由于1,2,3,在前面已经使用了,使用没有比4更小的了,有0*0!种

使用总共有2*3!+1*2!+0*1!+0*0!=14种排列方法比目标排列字典序小,则目标排列字典序为15(不要忘记加一)

公式:

其中k[i]表示对于第i位的a[i],a[i+1]到a[n]种比a[i]小的数字的个数

实现代码:

	cin>>n;
	fac[0]=1;
	for(int i=1;i<=n;i++)//预处理阶乘 
		fac[i]=fac[i-1]*i;
	int ans=1;//注意 
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		int k=0;//统计比a[i]小且没有用过的数字 
		for(int j=i+1;j<=n;j++) if(a[j]<a[i]) k++;
		ans+=k*fac[n-i];
	}
	cout<<ans;

 

逆康托展开


求有4位的全排列中,字典序序数为15的序列?

先把15减1,表示有14个排列比目标序列字典序小

考虑第一位:14 / 3!  = 2 ... ... 2 说明比第一位小的数有2个(算式第一个2表示的意义),所以第一位为3

考虑第二位:2  / 2!  = 1 ... ... 0  说明在第二位之后且小于第二位的数有1个,所以第二位为:2

考虑第三位: 0 / 1!  = 0 ... ... 0 说明在第三位之后且小于第三位的数没有,所以第三位为:1

考虑第四位:1,2,3,都使用了所以为4

实现代码:

	bool vis[maxn];//表示数字是否使用了
	memset(vis,0,sizeof(vis)); 
	cin>>n>>k; 
	fac[0]=1;
	for(int i=1;i<n;i++)//预处理阶乘 
		fac[i]=fac[i-1]*i;
	k--;//注意 
	int q,j,cnt; 
	for(int i=1;i<=n;i++){
		q=k/fac[n-i];
		k=k%fac[n-i];
		cnt=0;
		for(j=1;;j++){
			if(!vis[j]) cnt++;//统计 
			if(cnt>q) break;
		}
		a[i]=j;
		vis[j]=true;
	}
	for(int i=1;i<=n;i++) cout<<a[i]<<' ';