含重复元素的排列问题

问题描述：

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

求含重复元素的排列问题，首先先求出不含重复元素的全排列。根据分治法，我们求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

最后

以上就是隐形大象为你收集整理的含重复元素的排列问题的全部内容，希望文章能够帮你解决含重复元素的排列问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。