学习:
1.利用STL里的next_permutation()函数(对于n个数使用n!下就可以得出它的全排列额:
boolean next_permutation(a.begin(),a.end()) 该函数是以输入字符串中的字符所构建的按字典顺序全排列中,判断当前字符串之后是否还有下一个字符串 如果next_permutation的执行次数少于全排列的个数,返回true 例如 a="abc" 全排列有 "abc" "acb" "bac" "bca" "cab" "cba" 执行一次next_permutation 返回true a变成 "acb" 再执行一次next_permutation 返回true a变成 "bac" ... 当执行到a="cba" 时 由于这已经是全排列的最后一个字符串,所以 再次执行next_permutation 则返回false
2.首先看什么叫字典序,顾名思义就是按照字典的顺序(a-z, 1-9)。以字典序为基础,我们可以得出任意两个数字串的大小。
我的代码:
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int str[4]; //输入的四位数字。 int shu[10000][4],chu[1000][4],t,h; //t表示shu中元素个数,h表示chu中元素个数。 void painie(void);//对这四个数进行排列并储存在shu[]中,这里包含首位为0,和数字重复的情况。 void painie(void) { for(int i=0;i<24;++i)//由于是4!总情况故循环24次 { for(int j=0;j<=3;++j) { shu[t][j]=str[j]; } t++; next_permutation(str,str+4); //每次对str中的四个元素进行排列。 } } int main (void) { int kkk=0; while(scanf("%d%d%d%d",&str[0],&str[1],&str[2],&str[3])&&str[0]+str[1]+str[2]+str[3])//四个同时为零退出。 { if(kkk++) printf("\n");//在每组数据前面输出一个空行,但第一组数据没有。 memset(shu,0,sizeof(shu)); memset(chu,0,sizeof(chu)); t=0; h=0; //初始化。 painie(); /*for(int j=0;j<t;++j) { for(int i=0;i<4;++i) printf("%d",shu[j][i]); printf("\n");}*/ for(int k=0;k<t;) //扫描shu中所有元素。 { if(shu[k][0]!=0) { for(int ii=0;ii<1000;ii++)//如果这个元素在chu中已经存在了或者首位为0,就不要了,用goto跳过储存。 { if(shu[k][0]==chu[ii][0]&&shu[k][1]==chu[ii][1]&&shu[k][2]==chu[ii][2]&&shu[k][3]==chu[ii][3]) goto l1; } for(int jj=0;jj<4;jj++) { chu[h][jj]=shu[k][jj]; } h++; } l1: k++; } int mm=0; for(int j=0;j<h;++j) { if (chu[j][0]!=mm) { mm=chu[j][0];//记录不同的首位。 if(j) printf("\n"); //第一组数据前不要空行。 } else if(j) printf(" ");//第一个数据前不要空格,这样可以保证每行最后一个数据后面没有空格。 for(int i=0;i<4;++i) printf("%d",chu[j][i]); } printf("\n"); } return 0; }
以下为递归实现全排列:
/*µÝ¹éʵÏÖÈ«ÅÅÁУ¨22:44)*/ #include<stdio.h> #include<string.h> char a[5],b[129][5]; int ht=0;//¼Ç¼bÖÐÊý¾ÝÊýÁ¿¡£ void allsort( char str[],int n,int t); void swap(char str[],int a,int b); void allsort(char str[],int n,int t) { if(ht==0) { for(int i=0;i<5;i++) b[ht][i]=str[i]; ht++; } if(n-t!=1) { for(int k=t;k<n;k++) { swap(str,t,k); if(k!=t) { for(int i=0;i<5;i++) b[ht][i]=str[i]; ht++; } allsort(str,n,t+1); swap(str,t,k); } } } int main(void) { scanf("%s",a); int n=strlen(a),t=0; allsort(a,n,t); for(int i=0;i<ht;i++) { printf("%s",b[i]); printf(" "); } return 0; } void swap(char str[],int a,int b) { int c=str[a]; str[a]=str[b]; str[b]=c; }