参考：http://blog.sina.com.cn/s/blog_9b95c19e0101aqwn.html
Description
设R={ r1, r2, ……, rn }是要进行排列的n个元素。其中元素r1 ,r2 ,……,rn可能相同。试设计一个算法，列出R的所有不同排列。
给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。
Input
输入数据的的第1行是元素个数n，1≤n≤500。接下来的1行是待排列的n个元素。
Output
将计算出的n个元素的所有不同排列输出，每种排列占1行，最后1行中的数是排列总数。
Sample Input
4 aacc
Sample Output
aacc
acac
acca
caac
caca
ccaa
6
其实呢，这个问题和普通求全排列问题差不多，只是多了“判断是否重复字符”的过程而已。
下面的代码是原文作者写的，改为c版本。
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 long long ans; 5 int ok(char str[],int a ,int b ) //检测第b个元素是否能放在第a个位置 6 { 7 int i; 8 if(b>a) 9 { 10 //若是前面有一个元素a[i]与a[b]相等， 11 //那a[b]的值已经在第a个位置出现过，再放在这个地方就是重复了。 12 for(i=a;i<b;i++) 13 if(str[i]==str[b]) return 0; 14 } 15 return 1; 16 } 17 void perm(char str[],int k,int m) 18 { 19 char temp; 20 int i; 21 if(k==m) 22 { 23 ans++; 24 for(i=0;i<=m;i++) 25 printf("%c",str[i]); 26 printf("\n"); 27 return ; 28 } 29 else for(i=k;i<=m;i++) 30 if(ok(str,k,i)) //检测第i个元素是否能放在第k个位置 31 { 32 temp=str[k];str[k]=str[i];str[i]=temp;//swap(str[k],str[i]); 33 perm(str,k+1,m); 34 temp=str[k];str[k]=str[i];str[i]=temp;//swap(str[k],str[i]); 35 } 36 } 37 int main() 38 { 39 char str[505]; 40 int n,i; 41 scanf("%d",&n); 42 getchar(); 43 ans=0; 44 for(i=0;i<n;i++) 45 scanf("%c",&str[i]); 46 perm(str,0,n-1); 47 printf("%lld\n",ans); 48 return 0; 49 }
这段代码是对上述问题的求解。下面改一下上述代码，对n个可能含有重复元素的整数进行全排列。
1 //参考：http://blog.sina.com.cn/s/blog_9b95c19e0101aqwn.html 2 #include <stdio.h> 3 #include <stdlib.h> 4 5 long long ans; 6 int ok(int str[],int a ,int b ) //检测第b个元素是否能放在第a个位置 7 { 8 int i; 9 if(b>a) 10 { 11 //若是前面有一个元素a[i]与a[b]相等， 12 //那a[b]的值已经在第a个位置出现过，再放在这个地方就是重复了。 13 for(i=a;i<b;i++) 14 if(str[i]==str[b]) return 0; 15 } 16 return 1; 17 } 18 void perm(int str[],int k,int m) 19 { 20 int temp; 21 int i; 22 if(k==m) 23 { 24 ans++; 25 for(i=0;i<=m;i++) 26 printf("%-4d ",str[i]); 27 printf("\n"); 28 return ; 29 } 30 else for(i=k;i<=m;i++) 31 if(ok(str,k,i)) //检测第i个元素是否能放在第k个位置 32 { 33 temp=str[k];str[k]=str[i];str[i]=temp;//swap(str[k],str[i]); 34 perm(str,k+1,m); 35 temp=str[k];str[k]=str[i];str[i]=temp;//swap(str[k],str[i]); 36 } 37 } 38 int main() 39 { 40 int str[505]; 41 int n,i; 42 scanf("%d",&n); 43 44 ans=0; 45 for(i=0;i<n;i++) 46 scanf("%d",&str[i]); 47 perm(str,0,n-1); 48 printf("%lld\n",ans); 49 return 0; 50 }
至于 “对长度为n，可能含有重复元素的序列，选择r个元素做排列” 这样的问题，暂时没有想到比较好的思路了。
