蓝桥杯算法提高排列数（康拓展开的逆运算 || dfs || next_permutation(a,a+10)）

超、凢脫俗 2024-02-17 20:46 27阅读 0赞

算法提高 排列数

时间限制：1.0s 内存限制：256.0MB

问题描述

0、1、2三个数字的全排列有六种，按照字母序排列如下：  
　　012、021、102、120、201、210  
　　输入一个数n  
　　求0~9十个数的全排列中的第n个（第1个为0123456789）。

输入格式

一行，包含一个整数n

输出格式

一行，包含一组10个数字的全排列

样例输入

样例输出

0123456789

数据规模和约定

0 < n <= 10!

0ms通过

分析：康拓展开的逆运算 ；

如何判断给定一个位置，输出该位置上的数列，康拓展开的逆运算，例如：

\{1,2,3,4,5\}的全排列，并且已经从小到大排序完毕，请找出第96个数：

首先用96-1得到95

用95去除4! 得到3余23，即有3个数比该数位上的数字小，则该数位的数字为4；

用23去除3! 得到3余5，即有3个数比该数位上的数字小，理应为4，但4已在前面的高位中出现过，所以该数位的数字为5；

用5去除2!得到2余1，即有2个数比该数位上的数字小，则该数位的数字为3；

用1去除1!得到1余0，即有1个数比该数位上的数字小，则该数位的数字为2；

最后一个数只能是1；

所以这个数是45321

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    int a[12];
    int n;
    int jiecheng(int k){
    	int sum=1;
    	for(int i=1;i<=k;i++)
    	sum*=i;
    	return sum;
    }
    
    void cator(int n){
    	int c[12];
    	memset(c,0,sizeof(c));
    	for(int i=0;i<10;i++){
    	    int tmp=n/(jiecheng(9-i));
    		for(int j=0;j<=tmp;j++){
    			if(c[j])tmp++;
    		}
    		c[tmp]=1;
    		a[i]=tmp;
    		n%=jiecheng(9-i);
    	}
    }
    int main(){
        while(scanf("%d",&n)==1){
        	memset(a,-1,sizeof(a));
        	cator(n-1);
        	for(int i=0;i<10;i++)
        	printf("%d",a[i]);
        	printf("\n");
    	}
    	return 0;
    }

方法二：dfs（250ms）

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    int vis[12];
    int a[12];
    int n;
    
    void dfs(int cur){
    	if(cur==10){
    		n--;
    		if(n==0){
    			for(int i=0;i<10;i++)
    			printf("%d",a[i]);
    			printf("\n");
    		}
    		return ;
    	}
    	
    	for(int i=0;i<=9;i++){
    		if(!vis[i]){
    			vis[i]=1;
    			a[cur]=i;
    			dfs(cur+1);
    			vis[i]=0;
    		}
    	}
    }
    int main(){
    	while(scanf("%d",&n)==1){
    		memset(vis,0,sizeof(vis));
    		dfs(0);
    	}
    	return 0;
    }

方法三：应用STL中的next\_permutation()函数求下一个排列（187ms）

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int a[]={0,1,2,3,4,5,6,7,8,9};
    int n;
    
    int main(){
    	while(scanf("%d",&n)==1){
          for(int i=0;i<n-1;i++){
          	next_permutation(a,a+10);
    	  }
    	  for(int i=0;i<10;i++)
    	  printf("%d",a[i]);
    	  printf("\n");
    	}
    	return 0;
    }