LightOJ1060 nth Permutaiton 计数的思想

题目

Given a string of characters, we can permute the individual characters to make new strings. At first we order the string into alphabetical order. Then we start permuting it.

For example the string ‘abba’ gives rise to the following 6 distinct permutations in alphabetical order.

aabb 1

abab 2

abba 3

baab 4

baba 5

bbaa 6

Given a string, you have to find the nth permutation for that string. For the above case ‘aabb’ is the 1st and ‘baab’ is the 4th permutation.

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case contains a non empty string of lowercase letters with length no more than 20 and an integer n (0 < n < $2^{31}$).

题解

我们有逆康拓展开的思想,就是说,求长度为n的第k的一个排列(n从0开始).

比如说求长度为4的第5大的排列.

• 先考虑第一个数,如果为1,那么能确定这个排列一定比 $0X3!=0$个数大,如果为2的话,那么可以确定,这个排列一定比$1X3!=6$个数大所以第一位应该填1,然后求剩余3位数中第5大的排列.
• 考虑第二个数,按照上面分析,那么这该位应该为4,然后求剩余2位数中排第1大的数
• 那么最后的排列应该为:1432

那么这个题可以利用同样的思想,只不过要考虑要去重的问题,方法就是

​ 如果当前为x,那么我们就计算有多少个排列一定比它小,这样一直做下去就得到了答案

代码

#include<cstdio>
#include<cstring>
char s[25];
int cnt[500],sum[500];
long long  fac[25];
void init(){
	fac[0]=1;
	for(int i=1;i<=20;++i)fac[i]=fac[i-1]*i;
}
long long n;
long long calc(int ch){
	long long res=0;
	int sum=0;
	int x[500];
	for(int i='a';i<='z';++i){
		sum+=cnt[i];
		x[i]=cnt[i];
	}
	for(int i='a';i<ch;++i){
		if(!x[i])continue;//如果当前位选择i,会导致多少比他小(全排列的值)
		long long tmp=fac[sum-1];
		x[i]--;
		for(int i='a';i<='z';++i){
			tmp/=fac[x[i]];
		}
		res+=tmp;
		x[i]++;//还原x[i]
	}
	return res;
}
int len;
void dfs(int id,long long n){
	if(id==len){
		return ;
	}
	int ans='0',bigX=0;
	for(int i='a';i<='z';++i){
		if(!cnt[i])continue;
		long long x=calc(i);
		if(x<=n){
			ans=i;
			bigX=x;
		}
		else{
			break;
		}
	}
	printf("%c",ans);
	n-=bigX;
	cnt[ans]--;
	dfs(id+1,n);
}
int main(){
	int T;scanf("%d",&T);
	init();
	for(int test=1;test<=T;++test){
		scanf("%s%lld",s,&n);
		printf("Case %d: ",test);
		len=strlen(s);
		memset(cnt,0,sizeof(cnt));
		for(int i=0;i<len;++i)cnt[s[i]]++;
		long long maxN=fac[len];
		for(int i='a';i<='z';++i)maxN/=fac[cnt[i]];
		if(n>maxN){
			printf("Impossible\n");
			continue;
		}else{
			n--;//为了从0开始计数
			dfs(0,n);
			printf("\n");

		}
	}
	return 0;
}