有重复元素的排列问题

参考：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("
");
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
",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("
");
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
",ans);
49     return 0;
50 }

至于 “对长度为n，可能含有重复元素的序列，选择r个元素做排列” 这样的问题，暂时没有想到比较好的思路了。