有重复元素的全排列.doc

有重复元素的排列问题 1. 问题描述 设R={r1，r2，…rn}是要进行排列的n个元素。其中元素r1，r2，…rn可能相同。设计一个算法，列出R的所有不同排列。 算法设计：给定n及待排列的n个元素。计算出这n个元素的所有不同排列。 2. 算法流程分析 设计一个递归算法生成n个元素的全排列。设R={r1,r2,r3,……rn}的全排列为perm(R)，由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。 如果这组数有重复的元素，在准备开始第i个元素打头的全排列序列时，即Swap(R[k],R[i])之前，先判断第i个元素是否在前面元素R[k…i-1]中出现过，未出现过，此过程照旧继续，若出现过，这次以i元素打头的排列输出跳过。 设 list[]={0,0,1}，算法流程示意图如下： 3. 算法正确性证明 通过几组实例证明合法的输入可以得到正确的输出。实例见附录第2部分。 4. 算法复杂度分析 n个元素的全排列若不考虑重复元素，有n！种不同的全排列，则时间复杂度为O(n!)。若考虑重复元素，在最坏的情况下，重复元素出现的概率为0，则时间复杂度仍为O(n!)。 5.参考文献 [1] 王晓东编著，计算机算法设计与分析（第3版）。北京：电子工业出版社，2007.5，P11-12 6.附录 （1）可执行代码如下： #includeiostream.h templateclass Type void perm(Type list[],int k,int m) { if (k==m) { for (int i=0;i=m;i++) coutlist[i]; coutendl; } else { for(int i=k;i=m;i++) if(ch(list,k,i)) { swap(list[k],list[i]); perm(list,k+1,m); swap(list[k],list[i]); } } } templateclass Type inline void swap(Type a,Type b) { Type temp=a;a=b;b=temp; } void main() { int list[3]={0,1,1}; perm(list,0,2); } templateclass Type int ch(Type list[],int k,int i) {if(ik) for(int t=k;ti;t++) if(list[t]==list[i]) return 0; return 1; } （2）输入输出实例 输入1 3 5 5 输出如下： 1 3 5 5 1 5 3 5 1 5 5 3 3 1 5 5 3 5 1 5 3 5 5 1 5 1 3 5 5 1 5 3 5 3 1 5 5 3 5 1 5 5 1 3 5 5 3 1 P(0,2) S(0,0) P(1,2) S(0,0) S(0,2) P(1,2) S(0,2) S(0,1) P(1,2) S(0,1) 第一个元素第二个元素相同，舍弃 S(1,1) P(2,2) S(1,1) Count 0,0,1 Cout 0,1,0 S(1,2) P(2,2) S(1,2) S(1,1) P(2,2) S(1,1) S(1,2) P(2,2) S(1,2) 第二第三个元素相同，舍去 Cout 1,0,0