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

全排列 1 首先看最后兩個數(shù)4 5 它們的全排列為45和54 即以4開頭的5的全排列和以5開頭的4的全排列 由于一個數(shù)的全排列就是其本身 從而得到以上結(jié)果 2 再看后三個數(shù)3 4 5 它們的全排列為345 354 435 453 534 543六組數(shù) 即以3開頭的和4 5的全排列的組合 以4開頭的和3 5的全排列的組合和以5開頭的和3 4的全排列的組合 從而可以推斷 設(shè)一組數(shù)p r1 r2 r3 rn 全排列為perm p pn p rn 因此perm p r1perm p1 r2perm p2 r3perm p3 rnperm pn 當(dāng)n 1時perm p r1 為了更容易理解 將整組數(shù)中的所有的數(shù)分別與第一個數(shù)交換 這樣就總是在處理后n 1個數(shù)的全排列 兩個例子 123的全排列 首先遍歷元素 然后把遍歷到的每一個元素都和第一個元素交換第一個和第一個交換就是1和1交換最后還是123那么就形成了123213321這樣的3組 交換后再換回來還原成123因為后面的交換都是在123的基礎(chǔ)上交換的所以swap要寫2次 檢查每一組除了第一個之外的剩余元素 如果這些元素個數(shù)是2 那么就對這剩下的2個元素全排列就是123132 213231 3213122個元素的全排列很簡單就是把這2個元素交換位置就OK 兩個例子 1234的全排列 首先遍歷元素 然后把遍歷到的每一個元素都和第一個元素交換那么就形成了1234213432144231這樣的4組 檢查每一組除了第一個之外的剩余元素 如1234剩余的是234 發(fā)現(xiàn)是3個元素那么問題就轉(zhuǎn)換為求234的全排列了接下來也是一樣問題轉(zhuǎn)換為求134 214 231的全排列像這樣總是對除了第一個之外的元素全排列 每次元素的個數(shù)都在減少一個 求N個元素全排列最終就變成求2的元素的全排列了 求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 種 依次類推 若用一個數(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 3123132213231321312 n 4123412431324134214321423213421432314234124312413 321432413124314234123421423142134321431241324123 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 當(dāng)k指向最后元素時 遞歸終止 輸出相應(yīng)的字符串a(chǎn)否則i從k到n重復(fù)執(zhí)行 交換ak與ai range a k 1 n 交換ak與ai endrange 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 還有多個元素待排列 遞歸產(chǎn)生排列for inti k i m i Swap list k list i Perm list k 1 m Swap list k list i 為什么需要交換兩次 舉個例子比如現(xiàn)在數(shù)組的數(shù)據(jù)是123算法是這樣的1和3先交換變成了321然后遞歸