有重复元素的全排列

《有重复元素的全排列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、有重复元素的排列问题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个元素

2、是否在前面元素R[k…i-1]中出现过，未出现过，此过程照旧继续，若出现过，这次以i元素打头的排列输出跳过。设list[]={0,0,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)Count0,0,1Cout0,1,0S(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)第二第三个元素相同，舍去Cout1,0,03.算法正确

3、性证明通过几组实例证明合法的输入可以得到正确的输出。实例见附录第2部分。4.算法复杂度分析n个元素的全排列若不考虑重复元素，有n！种不同的全排列，则时间复杂度为O(n!)。若考虑重复元素，在最坏的情况下，重复元素出现的概率为0，则时间复杂度仍为O(n!)。5.参考文献[1]王晓东编著，计算机算法设计与分析（第3版）。北京：电子工业出版社，2007.5，P11-126.附录（1）可执行代码如下：#includetemplatevoidperm(Typelist[],intk,intm){if(k=

4、=m){for(inti=0;i<=m;i++)cout<inlinevoidswap(Type&a,Type&b){Typetemp=a;a=b;b=temp;}voidmain(){intlist[3]={0,1,1};perm(list,0,2);

5、}templateintch(Typelist[],intk,inti){if(i>k)for(intt=k;t