全排列算法設(shè)計和分析

全排列算法設(shè)計和分析第一頁，共8頁。兩個例子123的全排列

--首先遍歷元素,然后把遍歷到的每一個元素都和第一個元素交換

第一個和第一個交換就是1和1交換最后還是123

那么就形成了123

213

321這樣的3組

(交換后再換回來還原成123因為后面的交換都是在123的基礎(chǔ)上交換的所以swap要寫2次)

-檢查每一組除了第一個之外的剩余元素，如果這些元素個數(shù)是2，那么就對這剩下的2個元素全排列就是123132,

213231,3213122個元素的全排列很簡單就是把這2個元素交換位置就OK）

第二頁，共8頁。兩個例子1234的全排列

--首先遍歷元素,然后把遍歷到的每一個元素都和第一個元素交換

那么就形成了1234

2134

32144231這樣的4組

-檢查每一組除了第一個之外的剩余元素，如1234剩余的是234，發(fā)現(xiàn)是3個元素

那么問題就轉(zhuǎn)換為求234的全排列了

接下來也是一樣問題轉(zhuǎn)換為求134，214，231的全排列像這樣總是對除了第一個之外的元素全排列，每次元素的個數(shù)都在減少一個，求N個元素全排列最終就變成求2的元素的全排列了

第三頁，共8頁。求n個元素的全排列。分析：n=1輸出a1;n=2輸出a1a2;a2a1;n=3輸出a1a2a3;a1a3a2;a2a1a3;a2a3a1;

a3a2a1;a3a1a2;歸納：n=3時排列的分類（1）a1類：a1之后跟a2,a3的全排列；（2）a2類：a2之后跟a1,a3的全排列；（3）a3類：a3之后跟a2,a1的全排列。將(1)中的a1,a2互換位置，得到(2);將(1)中的a1,a3互換位置，得到(3).可以用循環(huán)重復(fù)執(zhí)行“交換位置，后跟剩余序列的所有排列”；對剩余的序列再使用該方法，直至沒有剩余序列——遞歸調(diào)用由排列組合的知識可知，n個元素的全排列共有n!種。n!可分解為n*(n-1)!種，而(n-1)!又分解為(n-1)(n-2)!種，依次類推。第四頁，共8頁。若用一個數(shù)組a[n]來保存1~n之間的n個自然數(shù)，對于i=1~n，每次使a[1]同a[i]交換后，對a[2]~a[n]中的n-1個元素進行全排列，然后再交換a[1]與a[i]的值，使它恢復(fù)為此次排列前的狀態(tài)；同樣，對于a[3]~a[n]區(qū)間內(nèi)的n-2個元素進行全排列，然后再把交換的元素交換回來；依次類推，直到對a[n]進行全排列時，輸出整個數(shù)組的值，即得到一種排列結(jié)果。n=3123132213231321312n=4

123412431324134214321423213421432314234124312413

321432413124314234123421

423142134321431241324123第五頁，共8頁。procedurerange(a,k,n)ifk=nthenprint(a)elsefori←ktondo{a[k]a[i];callrange(a,k+1,n);

a[k]a[i];}endifendrange；對于n個元素a=(a1a2……ak……an)，設(shè)過程range(a,k,n)是求a的第k到第n個元素的全排列。算法如下：procedurerange(a,k,n);

當k指向最后元素時，遞歸終止，輸出相應(yīng)的字符串a(chǎn)

否則

i從k到n重復(fù)執(zhí)行：交換ak與ai;range(a,k+1,n);

交換ak與ai;endrange;

第六頁，共8頁。

VoidPerm(Typelist[],intk,intm){//遞歸的產(chǎn)生前綴是list[0:k-1]后綴是list[k:m]的全排列的所有排列 if(k==m) {//只剩下一個元素 for(inti=0;i<=m;i++)cout<<list[i]; cout<<endl; } else//還有多個元素待