含重复元素的排列问题

92 阅读 0 评论 61 点赞

我是靠谱客的博主隐形大象，这篇文章主要介绍含重复元素的排列问题，现在分享给大家，希望可以做个参考。

复制代码

1
问题描述：

复制代码

1
2
3
设集合R={r1,r2,...,rn}是要进行排列的n个元素，其中r1,r2,...,rn可能相同。
试着设计一个算法，列出R的所有不同排列。
即，给定n以及待排的n个可能重复的元素。计算输出n个元素的所有不同排列。

大致思路：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
求含重复元素的排列问题，首先先求出不含重复元素的全排列。根据分治法，我们求n个元素的全排列，可以求出n-1个元素的全排列，然后再加上n的排列即可，当只有一个元素的时候，只有一种排列。然后依次合并子问题的解。
然后我们只要在此基础上加一个判断条件将重复的排列筛选掉即可。

复制代码/****************有重复元素的排列问题**************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
char a[100];
///待排列的字符串
int num;
///排列数
void swap(int i,int j){
///交换两个元素
char tmp;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
bool isok(int b,int i){
///判断是否重复
if(i > b){
for(int t = b; t < i; ++t){
if(a[t] == a[i]) return false;
}
}
return true;
}
void pailie(char s[],int begin,int end){
///递归排列函数
if(begin == end){
///剩余一个元素返回，打印结果
num++;
printf("%sn",s);
return;
}
for(int i = begin; i < end; i++){
///多于一个元素递归求解
if(isok(begin,i)){
swap(begin,i);
pailie(s,begin+1,end);
swap(begin,i);
}
}
return;
}
int main()
{
scanf("%s",a);
int l = (int)strlen(a);
pailie(a,0,l);
printf("%dn",num);
system("pause");
return 0;
}
///abcd
///aacc/****************有重复元素的排列问题**************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
char a[100];
///待排列的字符串
int num;
///排列数
void swap(int i,int j){
///交换两个元素
char tmp;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
bool isok(int b,int i){
///判断是否重复
if(i > b){
for(int t = b; t < i; ++t){
if(a[t] == a[i]) return false;
}
}
return true;
}
void pailie(char s[],int begin,int end){
///递归排列函数
if(begin == end){
///剩余一个元素返回，打印结果
num++;
printf("%sn",s);
return;
}
for(int i = begin; i < end; i++){
///多于一个元素递归求解
if(isok(begin,i)){
swap(begin,i);
pailie(s,begin+1,end);
swap(begin,i);
}
}
return;
}
int main()
{
scanf("%s",a);
int l = (int)strlen(a);
pailie(a,0,l);
printf("%dn",num);
system("pause");
return 0;
}
///abcd
///aacc