多重集的全排列算法研究-畢業(yè)論文

廈門大學本科畢業(yè)論文 I 本科畢業(yè)論文本科畢業(yè)論文 (科研訓練、畢業(yè)設計) 題題 目：多重集的全排列算法研究目：多重集的全排列算法研究 姓 名： 學 院：軟件學院 系：軟件工程系 專 業(yè)：軟件工程 年 級： 學 號： 指導教師（校內）： 職稱： 年 月 廈門大學本科畢業(yè)論文 II 多重集的全排列算法研究多重集的全排列算法研究 摘要摘要 全排列問題是一個經(jīng)典的數(shù)學問題，可分為一般無重復輸入的單重集排列問題和重 復輸入的多重集（Multiset）排列問題。在多重集中，同一個元素可多次出現(xiàn)，而在單重集 中，一個元素有且僅有出現(xiàn)一次。本文提出一種新的全排列產(chǎn)生算法（TWDRI） 。該算法不 僅能處理一般的單重集排列問題，而且能處理更為復雜的多重集排列問題，同時，TWDRI 算法適用于各種不同字符的輸入情況，具有廣泛的通用性。在此，我們進行了大量的模擬， 測試了從 10 位到 17 位的輸入情況，并與 11 種世界上已知的最快或最新的算法1234567 8910進行詳細的比較。模擬比較結果證明，本文提出的算法表現(xiàn)出相當優(yōu)秀的時間和空間 性能：在處理多重集問題上，速度是現(xiàn)存已知算法的 3 倍，內存開銷也僅僅在 800K 以下。 同時，本文也首次提出一種科學的計算方法，用于評估隨機輸入 N 位長度的多重集排列產(chǎn) 生的平均時間，具有歷史創(chuàng)新性。 關鍵詞關鍵詞 多重集 排列 算法 廈門大學本科畢業(yè)論文 III A Research into Multiset Permutation Algorithm Abstract We introduce TWDRI algorithm, the fastest new permutation technique for multiset permutations. A multiset is a set for which repeated elements are considered. The multiset permutation is a mathematical model. We consider any character string of length N as a multiset, which has k different characters, each has count n0, n1, , nk-1, respectively. Clearly, N = n0 + n1 + nk-1. For the input string, the multiset permutation generates all possible permutations without redundancy. When N=k, it is a pure permutation since n0 = n1 = nk-1 = 1. In general, we randomly input a character string with length N to generate its multiset permutation. We evaluate our permutation time and memory consumption by simulating strings with length N = 10, 11, 12, 13, 14, 15, 16, and 17, respectively. We calculate average multiset permutation time for all possible N N inputs with each fixed length N above. We compare our results with the eleven fastest known and/or well-known algorithms12345678910 in detail. The comparisons show our algorithm is three times faster than the fastest of them for multiset permutations. Our memory consumption is under 800Kb, which is very low for todays computers. We also introduce an evaluation method to calculate the average time of multiset permutations for all possible N N inputs with each fixed length N. Key words multiset permutation algorithm 廈門大學本科畢業(yè)論文 4 目錄目錄 第一章第一章 引言引言6 6 第二章第二章 研究背景研究背景7 7 2.12.1 多重集排列的相關定義多重集排列的相關定義 .7 2.22.2 全排列問題的研究歷史全排列問題的研究歷史 .7 2.2.1 單重集排列問題的研究歷史 .8 2.2.2 多重集排列問題的研究歷史 .8 2.32.3 歷史上的主要經(jīng)典算法歷史上的主要經(jīng)典算法 10 2.3.1 Heap 遞歸算法10 2.3.2 Ives 非遞歸算法11 2.3.3 基于格雷碼順序的多重集排列算法 13 第三章第三章 TWDRITWDRI 算法的基本模型算法的基本模型 1515 3.13.1 主要流程圖主要流程圖 15 3.23.2 算法產(chǎn)生排算法產(chǎn)生排列列的過程的過程 15 3.33.3 算法時間復雜度算法時間復雜度 16 3.43.4 算法的通用性和創(chuàng)新性算法的通用性和創(chuàng)新性 18 第四章第四章 模擬比較模擬比較2020 4.14.1 多重集排列的平均時間計算模型多重集排列的平均時間計算模型 20 4.1.1 基于隨機輸入的平均時間計算模型.20 4.1.2 計算模型的推導過程.20 4.1.3 平均時間計算公式.22 4.24.2 模擬比較結果模擬比較結果 23 4.2.1 多重集算法的時間和內存開銷比較.23 4.2.2 多重集算法在非重復輸入的情況下的時間比較.25 4.2.3 TWDRI 算法與其它單重集排列算法的時間和內存開銷比較.25 4.2.4 TWDRI 算法與其它多重集排列算法的比較趨勢分析.27 第五章第五章 結論結論2828 致謝語致謝語2929 參考文獻參考文獻3030 廈門大學本科畢業(yè)論文 5 Contents Chapter1 Introduction.6 Chapter2 Background7 2.1 The Related Definition of Multiset Permutation .7 2.2.1 The History of Pure Permutation .8 2.2.2 The History of Multiset Permutation8 2.2 The Study History of Multiset .7 2.3 Classical Algorithm.10 2.3.1 Heaps Recursive Algorithm.10 2.3.2 Ivess Iterative Algorithm.11 2.3.3 Multiset Permutation Algorithm Based on Grad-Code Order13 Chapter3 The TWDRI Model.15 3.1 Main Flowchart.15 3.3 The Process of Permutation Generation.15 3.3 Time Complexity.16 3.4 Universality and Innovation 18 Chapter4 Simulation and Comparison.20 4.1 Computing Model for Evalueation Mutliset Permutation20 4.1.1 Computing Model Based on Random Input.20 4.1.2 Derivation of Computing Model20 4.1.3 Computing Model for the Average Time of Mutliset Permutation22 4.2 The Result of Simulation and Comparison 23 4.2.1 Comparison of Average Time and Memory of Mutliset Permutation .23 4.2.2 Comparison of Average Time and Memory of Mutliset Permutation with Distinct Elements25 4.2.3 Comparison of Average Time and Memory of Pure Permutation .25 4.2.4 Speed Rations of TWDRI Algorithm to Others.27 Chapter5 Summary28 Acknowledgement 29 References .30 廈門大學本科畢業(yè)論文 6 第一章第一章 引言引言 全排列問題是一個經(jīng)典的數(shù)學問題，有著悠久的歷史。全排列問題的產(chǎn)生可以追溯到 十六世紀五十年代，早在 1960 年就有這一領域算法的總結性文章出現(xiàn)1112。一代算法宗師 Donald E. Knuth 在其經(jīng)典著作計算機程序設計藝術13一書中寫道：“事實上，排列 (permutations)問題在計算機領域非常重要。Vaughan Pratt 提議直接把它們叫做 perms。如果 Pratt 的建議得以實施的話，那么計算機教科書的厚度將變得薄一些（相應書的價格也會便宜 一點） ” 。雖然 Knuth 語帶幽默，但由此可見排列在計算機領域出現(xiàn)的頻率之高。正是因為排 列問題如此重要，所以在過去的幾十年里，一直以來有眾多的研究人員致力于該問題的研究。 本文正是在這種歷史背景下孕育而生的。 本文提出了一種新的快速產(chǎn)生全排列的算法（TWDRI） ，它不僅能處理一般的單重集排 列問題，而且能處理更為復雜的多重集排列問題。其通用性和快速性對于全排列在實際生活 中的應用具有深刻的意義，例如密碼學領域對輸入的一些數(shù)字或字符產(chǎn)生其對應的密碼，生 物醫(yī)學領域 DNA 所有的可能排列等等。 本文的第二章將詳細講述多重集的排列問題，第三章將給出 TWDRI 算法的基本模型， 第四章將首次提出基于隨機輸入的多重集排列的平均時間計算模型，并與 11 種世界上已知 的最快或最新的算法經(jīng)行模擬比較，從而得出結論：TWDRI 算法是當今世界上處理多重集 問題的最快算法。 廈門大學本科畢業(yè)論文 7 第二章第二章 研究背景研究背景 2.12.1 多重集排列的相關定義多重集排列的相關定義 定義定義 1 1（多重集的長度 N） 我們把 N 個字符長度的字符串 S 看成一個多重集，字符串 S 包含 k 個不同的字符，每個字符的個數(shù)分別為 n0, n1, , nk-1。顯然，N = n0 + n1 + nk-1。 當 N=k 時，我們把此時的多重集稱為單重集，因為此時 n0 = n1 = nk-1 = 1，每個不同字符 的個數(shù)有且僅有一個。即我們一般意義上的無重復輸入。 定義定義 2 2（重復個數(shù) n0, n1, , nk-1） 對于長度為 N，有 k 個不同字符，每個字符個數(shù)分別 為 n0, n1, , nk-1的多重集，我們把 n0, n1, , nk-1 稱為每個字符的重復個數(shù)。 定理定理 1 1（多重集的排列數(shù)） 令 S 是長度為 N 的多重集，它有 k 個不同的元素，每個元 素的重復數(shù)分別為 n0, n1, , nk-1，那么，多重集 S 的排列數(shù)=，其中 N = n0 + n1 011 ! !.! k N n nn + nk-1。 多重集排列是個數(shù)學模型，對于每一個輸入字符串，多重集排列應該無重復無遺漏地列 舉出所有的可能排列組合。通常，我們隨機輸入一個長度為 N 的字符串，希望多重集排列 算法能準確快速的產(chǎn)生所有可能的排列。 例如，當我們輸入的字符串為“0112”時，我們可以得到：N = 4, k =3, n0 =1, n1 =2, n2 = 1；其所有產(chǎn)生的排列數(shù)為=12，分別為： 4! 1!2!1! 0211，0112，0121，1210，1201，1021，1120，1102，1012，2011，2110，2101。 2.22.2 全排列問題的研究歷史全排列問題的研究歷史 大部分科學家，特別是計算機和數(shù)學領域的專家，當他們需要列舉所有可能性并核對所 希望結果的時候，經(jīng)常會碰到這樣或那樣的問題，事實上，這些問題都屬于全排列問題。單 重集排列和多重集排列在很多領域都有廣泛的應用，例如 DNA 排序，密碼學，運籌學，電 路設計，統(tǒng)計學和化學領域等等。 科學家們對于單重集排列和多重集排列的研究，已經(jīng)有 300 多年歷史了123456789 10 廈門大學本科畢業(yè)論文 8 111213141516171819202122232425262728293031323334353637383940414243444546 474849505152535455。對于單重集排列的產(chǎn)生算法，百年來可以說不勝枚舉，遺憾的是， 對于多重集排列，相關的算法就屈指可數(shù)，而對于兩種排列都適用的算法，百年來更是少之 又少。與此同時，大部分算法在分析方面都缺乏詳細的模擬和比較，例如計算平均時間部分。 最近，Takaoka 和 Violich 在其論文10中僅僅利用了兩個非常簡單的多重集例子（3,3,3,3,3 和 2,3,5,2,3）就拿他們的算法與 Korsh 和 LaFollette 的算法9進行比較分析，顯然，這種 比較方法是相當沒有說服力的。 2.2.12.2.1 單重集排列問題的研究歷史單重集排列問題的研究歷史 科學家們總是在尋求一種盡可能快的算法來產(chǎn)生單重集或多重集排列。關于單重集排列 問題，已知最早的算法于 1605 年在英國教堂產(chǎn)生的6，當時，教堂中的牧師用它來計算幾 口大鐘不同的撞擊順序，以此產(chǎn)生各種不同的音樂效果。其后，具有代表性的算法包括 M. B. Wells12的遞歸算法和 S. M. Johnson22，H. F. Trotte21具有突破意義的鄰位交換法。1973 年，G. Ehrlic 提出了一種減少內層循環(huán)的 loopless 算法33，隨后，不少研究者緊接著又發(fā)展 了這一算法14172432363739。另外兩種算法是字典序法11161923263031和隨機排列法11 13242528。一代算法大師 Robert Sedgewick 曾于 1977 年對各種單重集排列的產(chǎn)生算法做了 一個全面而深刻的研究3，其中，Sedgewick 指出，Heap1是當時最快的遞歸交換算法，同 時，Ives2是最快的非遞歸交換算法。在 2002 年，Sedgewick 又提出了一個 Heap 遞歸算法 的改進版本6，該算法通過直接排列后三位字符來加快總體排列產(chǎn)生的速度。 2.2.22.2.2 多重集排列問題的研究歷史多重集排列問題的研究歷史 與單重集排列相比，多重集排列算法的發(fā)展起步較晚。多重集的排列順序通常有兩種， 字典順序和格雷碼順序。所謂的格雷碼順序，即每相鄰兩個排列之間只有一個數(shù)位發(fā)生變化。 F. Ruskey 認為，按照格雷碼順序產(chǎn)生多重集排列的算法是在處理多重集排列問題中最快的 算法8。James F. Korsh 同 Paul S. Lipschutz 在結合 Johnsons 22和 Lehmers algorithms 25算 法的基礎上，首次提出了產(chǎn)生多重集排列的 loopness 算法4。在這個新算法中，多重集的排 列是以鏈表形式產(chǎn)生的，鏈表中的操作都是由指針來完成，其中包括 O(1)時間的交換操作。 兩年后，Takaoka 使用數(shù)組改進了這個 O(1)時間的算法5。Vajnovszki54進一步提出了一種 基于數(shù)組的少循環(huán)算法。2004 年，James F. Korsh 和 Paul S. LaFollette 提出一種新的 loopness 廈門大學本科畢業(yè)論文 9 算法9，與以往基于數(shù)組的算法不同，這個新算法僅僅需要長度大小的線性存儲。Takaoka 和 Violich 于 2006 年又提出一種僅僅使用數(shù)組就能在線性空間產(chǎn)生多重集排列的 MULTPERM 算法10，其聲稱，MULTPERM 算法比 James F. Korsh 和 Paul S. LaFollettede 的算法9更為簡單和有效，但是，遺憾的是，他僅僅使用了兩個非常簡單的多重集例子： 3,3,3,3,3和2,3,5,2,3 10。另外，盡管不少科學家對多重集排列問題都給出了精妙的算法， 但這些算法都始終沒有突破通過保存和判斷信息來防止重復輸出的思維藩籬。 排列問題的一個特點就是輸出規(guī)模受輸入規(guī)模的影響極大。我們假設計算機進行一次運 算就能給出一個排列（實際的算法不可能做到這點） 。對于一臺運算速度為百萬次每秒的計 算機， 給出 11 個元素的集合的所有 11！= 399168 個排列只需幾秒鐘的時間，而給出 17 個 元素的集合的所有 17！= 355687428096000 個排列則需要幾年。就算是當前最快的計算機， 其運算速度達到萬億次每秒，要計算出大于 20 個元素的集合的所有排列在時間上也顯得不 太可能。在科學研究中確實可能遇到較大規(guī)模的排列需求，除了配置高性能的計算機之外， 找到一種高性能的排列算法就顯得非常必要。 表 2-1 不同性能計算機在各種輸入規(guī)模下進行排列所需時間 N排列的個數(shù)排列的個數(shù)百萬百萬/秒秒十億十億/秒秒萬億萬億/秒秒 103628800 1139916800幾秒 12479001600幾分鐘 136227020800幾小時幾秒 1487178291200天分鐘 151307674368000幾周幾分鐘 1620922789888000幾個月幾小時幾秒 17355687428096000幾年幾天幾分鐘 186402373705728000幾個月幾小時 19121645100408832000幾年幾天 202432902008176640000月 微不足道的時間微不足道的時間 漫長的等待漫長的等待 廈門大學本科畢業(yè)論文 10 2.32.3 歷史上的主要經(jīng)典算法歷史上的主要經(jīng)典算法 在著名的算法大師 Robert Sedgewick 于 1977 年發(fā)表的研究文章中3，他比較了眾多關于 單重集排列算法，得到了如下結論， Heap1是最快的遞歸交換算法，同時， Ives2是最快 的非遞歸交換算法。這兩種算法都是基于交換實現(xiàn)的。而對于多重集排列問題，F(xiàn). Ruskey 認為，按格雷碼順序產(chǎn)生排列的算法是處理此類問題中最快的算法8。下面，本文將給出以 上三種算法的基本模型和排列產(chǎn)生過程。 2.3.12.3.1 HeapHeap 遞歸算法遞歸算法 Heap 算法在處理單重集問題上是最快的的遞歸算法，它是基于交換實現(xiàn)的，每次產(chǎn)生 一個排列時只交換兩個位置上的字符的位置，經(jīng)過遞歸，從而得到所有正確的排列。 定義定義 3 3（P數(shù)組） Pi是 N 位長度字符串中每一位的字符，i=1,2N。 定義定義 4 4（c數(shù)組） ci是調用遞歸函數(shù) Permutation( i )時內部控制循環(huán)的計數(shù)器，i=1, 2N。 偽代碼如下： proceduce Permutation( i:N ) begin i:=N; loop: ci:=1 while i2: i:=i-1 repeat; process; loop if ci1: i:=i-1 repeat； process； loop if ci 1 then BigGen( t-1 ); dirt:= not dirt; if dirt then offt:= offt-1 + numt-1 else offt:= offt -1; end of BigGen; procedure swap ( t,x,y : integer ); local b,temp: integer; begin if t 1 then BigGen( t-1 ); b:= offt-1; ax + b:=:ay + b; PrintIt; end of swap; 廈門大學本科畢業(yè)論文 14 基于格雷碼順序的排列產(chǎn)生結果如圖 2-3 和 2-4 所示: A B C A C B C A B C B A B C A B A C 圖 2-5 當 N=3 時，基于格雷碼的多重集排列算法的排列產(chǎn)生圖 A B C D B A C D D A B C A D B C A D C B D A C B D C A B D C B A C D B A C D A B C A D B A C D B A C B D C A B D C B A D C B D A B C D A B C A D A B D C B A D C B D A C B D C A D B C A D B A C 圖 2-6 當 N=4 時，基于格雷碼的多重集排列算法的排列產(chǎn)生圖 廈門大學本科畢業(yè)論文 15 第三章第三章 TWDRI 算法的基本模型算法的基本模型 3.13.1 主要流程圖主要流程圖 TWDRI 算法是一種新的快速的全排列產(chǎn)生算法。該算法能同時解決一般無重復輸入的 單重集排列問題和重復輸入的多重集（Multiset）排列問題。程序根據(jù)輸入字符串，自動選 擇處理單重集排列問題的 PurePermutation()函數(shù)，或者處理多重集排列問題的 MultisetPermutation()函數(shù)，從而，既滿足了輸入字符串的隨機性，又達到了快速處理兩種不 同集合的排列問題。 圖 3-1 是算法其主要流程圖： Start Input a string Initialization() N=k PurePermutation(N-1,0)MultisetPermutation(N-1,0) End YN 圖 3-1 TWDRI 算法的主要流程圖 3.23.2 算法產(chǎn)生排列的過程算法產(chǎn)生排列的過程 為了形象地表示出算法 TWDRI 產(chǎn)生排列的過程，我們通過以下兩個例子來具體說明。 廈門大學本科畢業(yè)論文 16 圖 3-2，圖 3-3 分別說明了當輸入是多重集 A,X,X 和1,2,3,3時排列產(chǎn)生的過程。其中， 線條上的數(shù)字表示排列產(chǎn)生的步驟。 A X X A X X 14 2 5 3 6 X 7 X 8 圖 3-2 輸入A,X,X的排列產(chǎn)生過程 1 1 2 23 31 1 3 3 2 2 10 1 19 14 11 3 3 2 1 1 3 3 3 3 34 3 3 3 31 1 7 9 5 6 8 3 3 3 3 1213 2 2 3 3 16 15 2 2 3 3 17 18 1 1 2 2 3 3 21 1 1 3 3 22 23 24 20 1 1 2 23 3 28 26 3 3 27 2 2 29 25 3 3 2 2 33 1 1 31 30 2 21 1 34 32 圖 3-3 輸入1,2,3,3的排列產(chǎn)生過程 3.33.3 算法時間復雜度算法時間復雜度 算法的計算時間 T(n)滿足： （3- 12 3 (1)*(3) ( ) (3) nT nCnCn T n Cn 廈門大學本科畢業(yè)論文 17 1） 輸入規(guī)模為 n3 的問題可由 n 個輸入規(guī)模為 n-1 的子問題構成。是對子問題 12 *CnC 結果進行分解和合并的花費，其中、為常數(shù)。當 n=3 求解問題的花費為，為常數(shù)。 1 C 2 C 3 C 3 C . . 12 (1)C nC 12 (1)C nC 12 (1)C nC 12 (2)C nC 12 (2)C nC 12 (2)C nC 12 (2)C nC 12 (2)C nC 12 Cn C 3 C . . . . . . . . . . . . . . . . . . n branches n-1 branchesn-1 branchesn-1 branches (1)4n n (1)n n 1 n . . . . . . 12 4CC 12 4CC 12 4CC . . . . 3 C 3 C . . 3 C 3 C 3 C 3 C 3 C 3 C 3 C 3 C 3 C (1)5n n 4 branches4 branches 4 branches 圖 3-4 的遞歸樹 12 ( )(1)*T nnT nCnC 從樹的根結點開始,根有 n 個分支，第二層的每個節(jié)點有 n-1 個分支，一直到倒數(shù)第二 層的每個節(jié)點有 2 個分支，共 n+1 層。樹的第一層有 1 個節(jié)點，第二層有 n 個節(jié)點，以下各 層依次節(jié)點數(shù)為 n(n-1)、n(n-1)(n-2),最后一層為 n!個。 接下來分析在每層的花銷。TWDRI 算法的最大特點在于，隨著遞歸層數(shù)的增加，子問 題的取值空間不斷縮小，因此，在每個節(jié)點上對子問題的分割和合并的花費也從第一層的 到最后一層的不斷下降。 12 *CnC 12 CC 本文的算法無需到達樹結構的最后一層，而在倒數(shù)第三層時便能輸出排列。因為在遞歸 樹中一層節(jié)點的數(shù)目與其以上所有祖先節(jié)點的數(shù)目之和相近，所以最低兩層的排除能帶來性 能上的巨大提高。 總的時間花費有： 121212 ( )()(1)(2)* (1).T nC nCC nC nC nCn n + 12 5 (4) n i CCi 3 4 n i Ci 1 4 (1)(1)(2).) n i C nn nn nni 廈門大學本科畢業(yè)論文 18 + 2 5 (1(1).) n i Cnn ni 3 4 n i Ci 1 111111111 * !(.) !(1)!(2)!(3)!2!1!1!2! Cn nnnnn + 2 111111111 * !(.) !(1)!(2)!3!2!1!1!2!3! Cn nnn 3 4 n i Ci + 12 11 11111111 * !()* !() !1!2!1!2!3! nn ii CnCn ini 3 ! 6 n C + 12112 1 1311 !()* !* ! !26 n i n CCCnCCn i 3 ! 6 n C + 1212 311 () !(1)* !* ! 26 CC n eCnCn 3 ! 6 n C （3- 123 5171 ()() ! 266 C eC eCn 2） 對于輸入元素個數(shù)為 n 的全排列問題，其輸出的規(guī)模為 n!。因此時間復雜度中的 n！是 由問題本身固有的內在特點所決定的。本文算法的時間復雜度最終可以表示為 C*n!(C 為常 數(shù))，即從漸進意義上已達到排列問題時間復雜度的理論下界。 在大多數(shù)時間復雜度的分析中，常數(shù) C 都是對程序中語句行數(shù)的計算。為了進行較為 精確的分析,我們采用了和 Ives 相同的方法，即計算程序中的賦值、數(shù)值運算、比較和下標 引用的使用次數(shù)。 3.43.4 算法的通用性算法的通用性和創(chuàng)新性和創(chuàng)新性 定義定義 9 9（Mappings數(shù)組） 對于長度為 N，有 k 個不同字符，每個字符個數(shù)分別為 n0, n1, , nk-1的字符多重集，我們引進數(shù)組 Mappings來映射 k 個不同字符。k 此時為 Mappings 數(shù)組的長度。Mappingsi = ni所對應的不同字符，當 i = 0, 1, 2, , k-1 時。 例如，當輸入字符串為“0112”時，我們可以得到： N = 4, k =3, n0 =1, n1 =2, n2 = 1; Mappings0 = 0, Mappings1 = 1, Mappings2 = 2。 同理，當輸入字符串為“abbc”時，我們可以得到： 廈門大學本科畢業(yè)論文 19 N = 4, k =3, n0 =1, n1 =2, n2 = 1; Mappings0 = a, Mappings1 = b, Mappings2 = c。 顯然，對于以上兩個例子，雖然輸入不同，但是，它們映射到了相同的數(shù)字多重集 0,1,1,2。 與已有算法不同，TWDRI 采用了 Mappings數(shù)組，將各個不同輸入字符一對一映射到 連續(xù)的自然數(shù)數(shù)組，排列過程中僅僅對此自然數(shù)組進行操作。由于最后排列的產(chǎn)生是根據(jù)自 然數(shù)與字符對應關系得到的，這樣，既解決了傳統(tǒng)的多重集問題，又滿足了一般字符的隨機 輸入，具有廣泛的通用性。 更為難得可貴的是，TWDRI 算法沒有進行換位，也沒有按照格雷碼順序產(chǎn)生排列，在 速度上就超越了原有已知的解決相同問題的最快算法，從而，打破了傳統(tǒng)解決單重集排列問 題中最快算法都是基于換位的一般看法，也打破了多重集問題中最快的排列產(chǎn)生方法是基于 格雷碼順序的論斷。這對全排列算法的研究來說，無疑是個巨大的突破，具有歷史創(chuàng)新性。 廈門大學本科畢業(yè)論文 20 第四章第四章 模擬比較模擬比較 4.14.1 多重集排列的平均時間計算模型多重集排列的平均時間計算模型 下面我們將首先給出基于隨機輸入的平均時間計算模型，并進行推導，從而得出多重集 排列的平均時間計算公式。 4.1.14.1.1 基于隨機輸入的平均時間計算模型基于隨機輸入的平均時間計算模型 為了全面客觀的比較各個多重集算法的性能，我們需要對隨機輸入長度為 N 的字符串 的所有情況進行測試。一個輸入的產(chǎn)生可以看成是從 N 個字符中每次抽取 1 個字符填滿 N 個有序格子。每個格子都有 N 種字符可選，所有共有 N N種輸入情況。 然而我們不必測試所有的 N N種輸入，因為其中有些輸入的排列時間是相同的。以長度 4(N4)為例，顯然輸入“AAAA”和“BBBB”進行排列時間相同，輸入“AABB”, “CCDD”和“BCBC”的排列時間也是一樣的。這樣我們就可以對所有的輸入情況進行分 類，把那些具有相同排列時間的輸入劃分到一類中，得到 D 種分類。最后，我們只需測試 每類中的一個輸入的排列時間 td，再將時間 td乘以該類輸入的出現(xiàn)概率，求和，就可以得到 該類所有輸入情況的平均排列時間 T，也即： （4-1） 1 0 ( )* D d d Tprobability of group dt 4.1.24.1.2 計算模型的推導過程計算模型的推導過程 下面將利用數(shù)論中整數(shù)分拆（或稱整數(shù)剖分）的理論來介紹 N N種輸入的分類過程。 事實上，我們可以把分類可以抽象為對正整數(shù) N 的分拆。正整數(shù) N 的分拆是指，把 N 表示為一個或多個正整數(shù)的無序和，其中，每一個無序和就是 N 的一個分拆。由于分拆成 的若干個正整數(shù)的順序是不重要的，因此我們總可以排列這些正整數(shù)，使得它們的順序從最 大到最小。例如正整數(shù) 4 對應的分拆為 4=4，4=3+1，4=2+2，4=2+1+1，4=1+1+1+1。 簡而言之，N 的一個分拆可以寫成： 廈門大學本科畢業(yè)論文 21 （4- 21 2 1 i aaa iiN （1） 2） (這個表達式是純符號性的；它的項既不是指數(shù)式，表達式也不是一個乘積)。 其中為非負整數(shù)，該數(shù)等于值為 i 的正整數(shù)的個數(shù)。當被寫成式（4-2）的形式時，若 i a 0，則項通常被省略，使用 這個記號，4 的分拆為：41，3111，22，2112，14。 i a i a i 的每種形式對應一種分類，則正整數(shù) 4 的分拆總共有 5 類，具體如下表 21 2 1 i aaa i 4-1 所示： 表 4-1 正整數(shù) 4 的分拆 d 字符串舉例字符串舉例 k= 1 n i i a 141AAAA1 23111AAAB2 322AABB2 42112AABC3 514ABCD4 顯然，應用這種分拆的分類思想，我們可以得到，為多重集問題中互不相同的字符 1 n i i a 的個數(shù) k，根據(jù)定義 2，每種分類中的各個字符的重復次數(shù) n0, n1, , nk-1也能輕松得出，即 中每個不為 0 的的下標項 i，也因此，此時 n0 n1nk-1 21 2 1 i aaa iiN （1） i a 至此，為了求得每種分類的出現(xiàn)概率，我們還需要計算每種分類包含的輸入情況的個數(shù)。 還是以長度 4 為例，不失一般性，假設組成輸入字符串的字符集合為A,B,C,D，每種分類 中組成該類一個輸入的不同字符個數(shù)為 k，而從字符集合中選取 k 個字符有種選法。表 4- k N C 1 第 4 行 k=1+2=3，所以共有=4 種選擇：ABC，ABD，ACD，BCD；對于一種選擇如 3 4 C ABC 我們還要考慮哪個字符重復出現(xiàn) 2 次：A 出現(xiàn) 2 次得到 AABC，B 出現(xiàn) 2 次得到 BBAC，C 出現(xiàn) 2 次得到 CCAB，因此要對每種選擇的字符進行排列，有排列個數(shù) =3；當 A 出現(xiàn) 2 次時，AABC，BAAC 和 BACA 也是不同的，排列個 1 !/ N i kai 3!/(1!*2!) 廈門大學本科畢業(yè)論文 22 數(shù)為=12。所以，當 N=4，k=3，分拆 2112所對應的分類總 11 !/( !) a N i jk Ni 4!/(2!*1!*1!) 共有 4*3*12 種輸入情況，其在所有 44種隨機輸入中所占的概率為 4*3*12/44。 所以，每個分類中所有輸入情況的出現(xiàn)概率為： （4- 111 (!/!)(!/( !)/ d a NN i kn Nd ikj probability of group dCkaNiN i 3） 4.1.34.1.3 平均時間計算公式平均時間計算公式 為了方便應用與理解，我們根據(jù)以上推導，總結如下： 假定一個輸入中有 k 個不同的字符，每個字符的個數(shù)分別為 n0, n1, , nk-1，顯然，N = n0 + n1 + nk-1。不失一般性，我們假定 D 為 n0, n1, , nk-1的不同拆分數(shù)，其中 n0 n1nk-1， 并且 N = n0 + n1 + nk-1。此時，對于長度為 N 的字符串的所有可能 N N種 輸入，就分成了 D 種不同的類別。我們用來表示 D 種分類中的不 ,0,1,2,1 ,., d dddd k nnnn 同組合，其中，d = 0, 1, , D-1.對于每一種分類，它們有相同的排列時間，即 td，其中，d = 0, 1, , D-1。 對于一個固定的 d 值，我們用 rd來表示中不同數(shù)字的個數(shù)， ,0,1,2,1 ,., d dddd k nnnn 用來分別記錄每個 rd值的個數(shù)。表 4-2 顯示了當 N=4 時N N種輸入中 ,0,1,1 ,., d ddd r mmm 分別帶有一個代表性例子的 5 種分類。 表 4-2 當N=4 的N N種輸入的 5 種分類 d字符串舉例字符串舉例kd ,0,1,1 ,., d ddd k nnn ,0,1,1 ,., d ddd r mmm td 00000141t1 1000123, 11, 1t2 2001122, 22t3 3001232, 1, 11, 2t4 4012341, 1, 1, 14t5 對于 N N種可能輸入的平均排列時間為： 1 0( ) D d d probability of group d t 11 1 , 000 (!/!)(!/!)/ dd d rk D kN Ndd jd jd djj CkmNntN 廈門大學本科畢業(yè)論文 23 （4- 1 1 1 , 000 (!/)()/!)(!)( ! d d k r D d kN dd Nd jd j djj NCnm Nkt 4） 例如，當N = 4（參見表4-2） ，隨機輸入長度為 4 的字符串的平均排列時間為： 03124 0011223344 0,00,01,01,11,01,12,02,02,13,03,13,03,13,24,04,04,14,24,3 ! ! kkkkk NNNNN N C k tC k tC k tC k tC k tN Nmnmmnnmnnmmnnnmnnnn 13224 4043414244 4 1!3!2!2!4!4! 41!4!1!1!3!1!2!2!2!1!2!2!1!1!4!1!1!1!1! CtCtCtCtCt 01234 13993 6416641632 ttttt 4.24.2 模擬比較結果模擬比較結果 借鑒以往大型模擬比較的經(jīng)驗56，我們把 TWDRI 算法同 11 種已知最快或最新的算法 進行模擬比較。為保證比較的的科學性、準確性和公平性，所有的算法都用遵循 ANSI C 標 準的 C 語言實現(xiàn)，并且運行在相同配置的計算機上（Pentium 4，CPU 2.93 GHz，1 GB 內存） 。 從通用性出發(fā)，我們模擬測試選擇的字符串從字符 0-9 和 a-j 中選出。例如，當模擬單 重集算法時，如果 N=5，模擬測試的字符串為 “01234；如果 N=17，模擬測試的字符串則 為“0123456789abcdefg”。 以下是縮寫說明: Heap63: 遞歸交換算法1 Heap63: 非遞歸交換算法1 Ives 76:非遞歸交換算法2 JT: loopless Johnson-Trotter 算法(算法 3b)3 JTLLC03: Jeeve Technologies LLC 算法7 KL97: Korsh 和 Lipschutz 常數(shù)時間算法4 KL04: Korsh 和 LaFollette 基于數(shù)組的少循環(huán)算法9 Ruskey 03: Ruskey 算法53 Sedgewick02: Sedgewick 算法6 廈門大學本科畢業(yè)論文 24 Takaoka99: Takaoka 的 O(1)算法5 TV06: Takaoka 和 Violich 的算法10 4.2.14.2.1 多重集算法的時間和內存開銷比較多重集算法的時間和內存開銷比較 表 4-3 和圖 4-1 說明 TWDRI 算法在處理多重集問題中，速度至少是其它 5 種算法中任 何一種的 3 倍。表 4-4 則說明，相對其它算法而言，TWDRI 算法的內存開銷是比較小的。 因此，顯而易見的，同各種多重集排列算法相比，TWDRI 算法表現(xiàn)出相當優(yōu)秀的時間和空 間性能。 表 4-3 多重集排列算法的平均時間比較 (單位：毫秒) NTWDRI KL97KL04Ruskey03Takaoka 99 TV06 1117 139 220 52 440 149 12157 1,318 2,036 479 4,202 1,369 131,488 12,695 20,389 4,779 42,175 13,729 1415,402 141,908 218,824 51,654 457,865 146,359 15171,967 1,568,173 2,532,981 595,249 5,234,257 1,684,183 162,041,640 7,411,56 4 0.00E+00 5.50E+05 1.10E+06 1.65E+06 2.20E+06 2.75E+06 3.30E+06 3.85E+06 4.40E+06 4.95E+06 5.50E+06 1112131415 (N) (Time/ms) TWDRIKL97KL04Ruskey 03Takaoka 99TV06 圖4-1 多重集全排列算法的平均時間比較 表 4-4 多重集全排列算法內存的峰值平均值比較 (單位：KB) 廈門大學本科畢業(yè)論文 25 NTWDRI KL97KL04Ruskey03Takaoka 99 TV06 11768768813813780780728728788788864864 12772772832832788788732732792792868868 13776776859859792792736736800800876876 14772772897897796796740740812812888888 15784784941941804804748748824824896896 16800800752752 4.2.24.2.2 多重集算法在非重復輸入的情況下的時間比較多重集算法在非重復輸入的情況下的時間比較 表 4-5 和圖 4-2 說明，在非重復輸入的情況下，TWDRI 算法的速度是其它 5 種多重集 算法中最快算法的 9 倍。 表 4-5 多重集全排列算法在無重復輸入下的時間比較 (單位：毫秒) NTWDRIKL97KL04Ruskey 03Takaoka 99TV06 10017223463547203 11791,9842,7197666,0162,125 1296923,42234,3758,56572,23425,985 1312,438290,375459,907118,229965,76533