算法|含重复元素的排列问题算法|分治

问题描述：

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

大致思路：

求含重复元素的排列问题，首先先求出不含重复元素的全排列。根据分治法，我们求n个元素的全排列，可以求出n-1个元素的全排列，然后再加上n的排列即可，当只有一个元素的时候，只有一种排列。然后依次合并子问题的解。
然后我们只要在此基础上加一个判断条件将重复的排列筛选掉即可。

【算法|含重复元素的排列问题】

/****************有重复元素的排列问题**************************************/ #include #include #include #include #include #include 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("%s\n",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("%d\n",num); system("pause"); return 0; } ///abcd ///aacc