有重復(fù)元素的排列問(wèn)題

1、有重復(fù)元素的排列問(wèn)題有重復(fù)元素的排列問(wèn)題問(wèn)題描述：?jiǎn)栴}描述： 設(shè)R=r1,r2,rn是要進(jìn)行排列的n個(gè)元素，其中r1,r2,rn可能相同。試設(shè)計(jì)一個(gè)算法，列出R的所有不同排列。編程任務(wù)編程任務(wù)： 給定以及待排列的個(gè)元素。計(jì)算出這個(gè)元素的所有不同排列。有重復(fù)元素的排列問(wèn)題R R全排列歸納定義全排列歸納定義： 當(dāng)n=1時(shí)，Perm(R)=(r)，其中r是集合R中唯一的元素； 當(dāng)n1是，Perm(R)由(r1)Perm(R1)，(r2)Perm(R2) ，(rn)Perm(Rn)有構(gòu)成。其中Ri=R-ri，(ri) Perm(Ri) 表示在全排列Ri的每一個(gè)排列前加上前綴ri得到的排列。R R全排列

2、遞歸算法全排列遞歸算法： 定義過(guò)程：void perm(char a,int k,int m)。在過(guò)程中將ak:m中的每個(gè)元素分別與ak中的元素交換，然后遞歸調(diào)用ak+1:m的全排列，并將計(jì)算結(jié)果做a0:k為的后綴。重復(fù)元素的解決方法重復(fù)元素的解決方法：由于ak:m中各元素可能相同，因此在與ak中的元素交換之前要先判斷該元素是否已經(jīng)使用過(guò)。本算法采用鏈表來(lái)存儲(chǔ)各位元素的使用情況。有重復(fù)元素的排列問(wèn)題有重復(fù)元素的排列問(wèn)題算例算例： 輸入：5 aabcc k=0,i=0鏈表used=ai=a,不在表used中，將該元素添加到used中，并調(diào)用調(diào)用ak+1:m的全排列k=0,i=1鏈表used=aa

3、i=a, 在表used中找到，說(shuō)明以ai為前綴的排列已經(jīng)輸出。有重復(fù)元素的排列問(wèn)題k=0,i=2鏈表used=aai=b,不在表used中，將該元素添加到used中，并調(diào)用調(diào)用ak+1:m的全排列k=0,i=3鏈表used=abai=c, 不在表used中，將該元素添加到used中，并調(diào)用調(diào)用ak+1:m的全排列k=0,i=4鏈表used=abcai=c, 在表used中找到，說(shuō)明以ai為前綴的排列已經(jīng)輸出。算法實(shí)現(xiàn)#include void perm(char a,int k,int m) if (k=m) /排列完成，輸出排列排列完成，輸出排列 else list used; for (int i=k;i=m;i+) bool found=false; list:iterator pos=find(used.begin(),used.end(),ai); if (pos!=used.end() found=true; if (!found) used.p