Repeat-elements-arranged-issue.zip_Arranged_site:www.pudn.com

8594 有重复元素的排列问题 时间限制:1000MS 内存限制:1000K 提交次数:1610 通过次数:656 题型: 编程题 语言: 无限制 Description 设集合R={r1,r2,...,rn}是要进行排列的n个元素，其中r1,r2,...,rn可能相同。 试着设计一个算法，列出R的所有不同排列。 即，给定n以及待排的n个可能重复的元素。计算输出n个元素的所有不同排列。 输入格式 第1行是元素个数n，1<=n<=15。接下来的1行是待排列的n个元素，元素中间不要加空格。 输出格式 程序运行结束时，将计算输出n个元素的所有不同排列。最后1行中的数是排列总数。 （说明： 此题，所有计算出的排列原本是无所谓顺序的。但为了容易评判，输出结果必须唯一！ 现做约定：所有排列的输出顺序如课本例2-4的程序段的输出顺序，区别仅是这道题是含重复元素。） 输入样例 4 aacc 输出样例 aacc acac acca caac caca ccaa 6 提示 课本上有“递归”实现无重复元素全排列的源程序。 稍加修改即可满足此题要求。 在递归产生全排列的那段程序开始之前， 加一个判断：判断第i个元素是否在list[k,i-1]中出现过。 Permpp(char list[], int k, int m) { ...... for (int i=k; i<=m; i++) { if (Findsame(list,k,i))//判断第i个元素是否在list[k,i－1]中出现过 continue; Swap (list[k], list[i]); Permpp(list, k+1, m); Swap (list[k], list[i]); } } ********************************************************* #include<stdio.h> #include<malloc.h> int count=0; void Swap(char* a,char* b){ char temp=*a; *a=*b; *b=temp; } int Permpp(char list[],int k,int m){ int i,j,flag; if(k==m){ for(i=0;i<=m;i++) printf("%c",list[i]); printf("\n"); count++; } else for(i=k;i<=m;i++){ for(j=k,flag=1;j<i;j++){ if(list[j]==list[i]) { flag=0; break; } } if(flag==1){ Swap(list+k,list+i); Permpp(list,k+1,m); Swap(list+k,list+i); } } return count; } int main(){ int n,count1; char *list; do{ scanf("%d",&n); }while(n<1||n>15); list=(char*)malloc(n*sizeof(char)); scanf("%s",list); count1=Permpp(list,0,n-1); printf("%d\n",count1); return 0; } **************************************** #include <stdio.h> int c=0; void Swap(char &x,char &y){ char z; z=x; x=y; y=z; } int Findsame(char a[],int k,int i){ int j; for(j=k;j<i;j++) if(a[i]==a[j]) return 1; return 0; } void Perm(char a[],int k,int m){ int i; if(k==m) { for(i=0;i<=m;i++) printf("%c",a[i]); c++; printf("\n"); } else { for(i=k;i<=m;i++) { if(Findsame(a,k,i)) continue; Swap(a[k],a[i]); Perm(a,k+1,m); Swap(a[k],a[i]); } } } int main(){ int n,i; char a[15]; scanf("%d",&n); getchar(); for(i=0;i<n;i++) scanf("%c",&a[i]); Perm(a,0,n-1); printf("%d\n",c); return 0; }