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

廈門(mén)大學(xué)本科畢業(yè)論文 I 本科畢業(yè)論文本科畢業(yè)論文 (科研訓(xùn)練、畢業(yè)設(shè)計(jì)) 題題 目：多重集的全排列算法研究目：多重集的全排列算法研究 姓 名： 學(xué) 院：軟件學(xué)院 系：軟件工程系 專(zhuān) 業(yè)：軟件工程 年 級(jí)： 學(xué) 號(hào)： 指導(dǎo)教師（校內(nèi)）： 職稱(chēng)： 年 月 廈門(mén)大學(xué)本科畢業(yè)論文 II 多重集的全排列算法研究多重集的全排列算法研究 摘要摘要 全排列問(wèn)題是一個(gè)經(jīng)典的數(shù)學(xué)問(wèn)題，可分為一般無(wú)重復(fù)輸入的單重集排列問(wèn)題和重 復(fù)輸入的多重集（Multiset）排列問(wèn)題。在多重集中，同一個(gè)元素可多次出現(xiàn)，而在單重集 中，一個(gè)元素有且僅有出現(xiàn)一次。本文提出一種新的全排列產(chǎn)生算法（TWDRI） 。該算法不 僅能處理一般的單重集排列問(wèn)題，而且能處理更為復(fù)雜的多重集排列問(wèn)題，同時(shí)，TWDRI 算法適用于各種不同字符的輸入情況，具有廣泛的通用性。在此，我們進(jìn)行了大量的模擬， 測(cè)試了從 10 位到 17 位的輸入情況，并與 11 種世界上已知的最快或最新的算法1234567 8910進(jìn)行詳細(xì)的比較。模擬比較結(jié)果證明，本文提出的算法表現(xiàn)出相當(dāng)優(yōu)秀的時(shí)間和空間 性能：在處理多重集問(wèn)題上，速度是現(xiàn)存已知算法的 3 倍，內(nèi)存開(kāi)銷(xiāo)也僅僅在 800K 以下。 同時(shí)，本文也首次提出一種科學(xué)的計(jì)算方法，用于評(píng)估隨機(jī)輸入 N 位長(zhǎng)度的多重集排列產(chǎn) 生的平均時(shí)間，具有歷史創(chuàng)新性。 關(guān)鍵詞關(guān)鍵詞 多重集 排列 算法 廈門(mén)大學(xué)本科畢業(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 廈門(mén)大學(xué)本科畢業(yè)論文 4 目錄目錄 第一章第一章 引言引言6 6 第二章第二章 研究背景研究背景7 7 2.12.1 多重集排列的相關(guān)定義多重集排列的相關(guān)定義 .7 2.22.2 全排列問(wèn)題的研究歷史全排列問(wèn)題的研究歷史 .7 2.2.1 單重集排列問(wèn)題的研究歷史 .8 2.2.2 多重集排列問(wèn)題的研究歷史 .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)生排列列的過(guò)程的過(guò)程 15 3.33.3 算法時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度 16 3.43.4 算法的通用性和創(chuàng)新性算法的通用性和創(chuàng)新性 18 第四章第四章 模擬比較模擬比較2020 4.14.1 多重集排列的平均時(shí)間計(jì)算模型多重集排列的平均時(shí)間計(jì)算模型 20 4.1.1 基于隨機(jī)輸入的平均時(shí)間計(jì)算模型.20 4.1.2 計(jì)算模型的推導(dǎo)過(guò)程.20 4.1.3 平均時(shí)間計(jì)算公式.22 4.24.2 模擬比較結(jié)果模擬比較結(jié)果 23 4.2.1 多重集算法的時(shí)間和內(nèi)存開(kāi)銷(xiāo)比較.23 4.2.2 多重集算法在非重復(fù)輸入的情況下的時(shí)間比較.25 4.2.3 TWDRI 算法與其它單重集排列算法的時(shí)間和內(nèi)存開(kāi)銷(xiāo)比較.25 4.2.4 TWDRI 算法與其它多重集排列算法的比較趨勢(shì)分析.27 第五章第五章 結(jié)論結(jié)論2828 致謝語(yǔ)致謝語(yǔ)2929 參考文獻(xiàn)參考文獻(xiàn)3030 廈門(mén)大學(xué)本科畢業(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 廈門(mén)大學(xué)本科畢業(yè)論文 6 第一章第一章 引言引言 全排列問(wèn)題是一個(gè)經(jīng)典的數(shù)學(xué)問(wèn)題，有著悠久的歷史。全排列問(wèn)題的產(chǎn)生可以追溯到 十六世紀(jì)五十年代，早在 1960 年就有這一領(lǐng)域算法的總結(jié)性文章出現(xiàn)1112。一代算法宗師 Donald E. Knuth 在其經(jīng)典著作計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)13一書(shū)中寫(xiě)道：“事實(shí)上，排列 (permutations)問(wèn)題在計(jì)算機(jī)領(lǐng)域非常重要。Vaughan Pratt 提議直接把它們叫做 perms。如果 Pratt 的建議得以實(shí)施的話(huà)，那么計(jì)算機(jī)教科書(shū)的厚度將變得薄一些（相應(yīng)書(shū)的價(jià)格也會(huì)便宜 一點(diǎn)） ” 。雖然 Knuth 語(yǔ)帶幽默，但由此可見(jiàn)排列在計(jì)算機(jī)領(lǐng)域出現(xiàn)的頻率之高。正是因?yàn)榕?列問(wèn)題如此重要，所以在過(guò)去的幾十年里，一直以來(lái)有眾多的研究人員致力于該問(wèn)題的研究。 本文正是在這種歷史背景下孕育而生的。 本文提出了一種新的快速產(chǎn)生全排列的算法（TWDRI） ，它不僅能處理一般的單重集排 列問(wèn)題，而且能處理更為復(fù)雜的多重集排列問(wèn)題。其通用性和快速性對(duì)于全排列在實(shí)際生活 中的應(yīng)用具有深刻的意義，例如密碼學(xué)領(lǐng)域?qū)斎氲囊恍?shù)字或字符產(chǎn)生其對(duì)應(yīng)的密碼，生 物醫(yī)學(xué)領(lǐng)域 DNA 所有的可能排列等等。 本文的第二章將詳細(xì)講述多重集的排列問(wèn)題，第三章將給出 TWDRI 算法的基本模型， 第四章將首次提出基于隨機(jī)輸入的多重集排列的平均時(shí)間計(jì)算模型，并與 11 種世界上已知 的最快或最新的算法經(jīng)行模擬比較，從而得出結(jié)論：TWDRI 算法是當(dāng)今世界上處理多重集 問(wèn)題的最快算法。 廈門(mén)大學(xué)本科畢業(yè)論文 7 第二章第二章 研究背景研究背景 2.12.1 多重集排列的相關(guān)定義多重集排列的相關(guān)定義 定義定義 1 1（多重集的長(zhǎng)度 N） 我們把 N 個(gè)字符長(zhǎng)度的字符串 S 看成一個(gè)多重集，字符串 S 包含 k 個(gè)不同的字符，每個(gè)字符的個(gè)數(shù)分別為 n0, n1, , nk-1。顯然，N = n0 + n1 + nk-1。 當(dāng) N=k 時(shí)，我們把此時(shí)的多重集稱(chēng)為單重集，因?yàn)榇藭r(shí) n0 = n1 = nk-1 = 1，每個(gè)不同字符 的個(gè)數(shù)有且僅有一個(gè)。即我們一般意義上的無(wú)重復(fù)輸入。 定義定義 2 2（重復(fù)個(gè)數(shù) n0, n1, , nk-1） 對(duì)于長(zhǎng)度為 N，有 k 個(gè)不同字符，每個(gè)字符個(gè)數(shù)分別 為 n0, n1, , nk-1的多重集，我們把 n0, n1, , nk-1 稱(chēng)為每個(gè)字符的重復(fù)個(gè)數(shù)。 定理定理 1 1（多重集的排列數(shù)） 令 S 是長(zhǎng)度為 N 的多重集，它有 k 個(gè)不同的元素，每個(gè)元 素的重復(fù)數(shù)分別為 n0, n1, , nk-1，那么，多重集 S 的排列數(shù)=，其中 N = n0 + n1 011 ! !.! k N n nn + nk-1。 多重集排列是個(gè)數(shù)學(xué)模型，對(duì)于每一個(gè)輸入字符串，多重集排列應(yīng)該無(wú)重復(fù)無(wú)遺漏地列 舉出所有的可能排列組合。通常，我們隨機(jī)輸入一個(gè)長(zhǎng)度為 N 的字符串，希望多重集排列 算法能準(zhǔn)確快速的產(chǎn)生所有可能的排列。 例如，當(dāng)我們輸入的字符串為“0112”時(shí)，我們可以得到：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 全排列問(wèn)題的研究歷史全排列問(wèn)題的研究歷史 大部分科學(xué)家，特別是計(jì)算機(jī)和數(shù)學(xué)領(lǐng)域的專(zhuān)家，當(dāng)他們需要列舉所有可能性并核對(duì)所 希望結(jié)果的時(shí)候，經(jīng)常會(huì)碰到這樣或那樣的問(wèn)題，事實(shí)上，這些問(wèn)題都屬于全排列問(wèn)題。單 重集排列和多重集排列在很多領(lǐng)域都有廣泛的應(yīng)用，例如 DNA 排序，密碼學(xué)，運(yùn)籌學(xué)，電 路設(shè)計(jì)，統(tǒng)計(jì)學(xué)和化學(xué)領(lǐng)域等等。 科學(xué)家們對(duì)于單重集排列和多重集排列的研究，已經(jīng)有 300 多年歷史了123456789 10 廈門(mén)大學(xué)本科畢業(yè)論文 8 111213141516171819202122232425262728293031323334353637383940414243444546 474849505152535455。對(duì)于單重集排列的產(chǎn)生算法，百年來(lái)可以說(shuō)不勝枚舉，遺憾的是， 對(duì)于多重集排列，相關(guān)的算法就屈指可數(shù)，而對(duì)于兩種排列都適用的算法，百年來(lái)更是少之 又少。與此同時(shí)，大部分算法在分析方面都缺乏詳細(xì)的模擬和比較，例如計(jì)算平均時(shí)間部分。 最近，Takaoka 和 Violich 在其論文10中僅僅利用了兩個(gè)非常簡(jiǎn)單的多重集例子（3,3,3,3,3 和 2,3,5,2,3）就拿他們的算法與 Korsh 和 LaFollette 的算法9進(jìn)行比較分析，顯然，這種 比較方法是相當(dāng)沒(méi)有說(shuō)服力的。 2.2.12.2.1 單重集排列問(wèn)題的研究歷史單重集排列問(wèn)題的研究歷史 科學(xué)家們總是在尋求一種盡可能快的算法來(lái)產(chǎn)生單重集或多重集排列。關(guān)于單重集排列 問(wèn)題，已知最早的算法于 1605 年在英國(guó)教堂產(chǎn)生的6，當(dāng)時(shí)，教堂中的牧師用它來(lái)計(jì)算幾 口大鐘不同的撞擊順序，以此產(chǎn)生各種不同的音樂(lè)效果。其后，具有代表性的算法包括 M. B. Wells12的遞歸算法和 S. M. Johnson22，H. F. Trotte21具有突破意義的鄰位交換法。1973 年，G. Ehrlic 提出了一種減少內(nèi)層循環(huán)的 loopless 算法33，隨后，不少研究者緊接著又發(fā)展 了這一算法14172432363739。另外兩種算法是字典序法11161923263031和隨機(jī)排列法11 13242528。一代算法大師 Robert Sedgewick 曾于 1977 年對(duì)各種單重集排列的產(chǎn)生算法做了 一個(gè)全面而深刻的研究3，其中，Sedgewick 指出，Heap1是當(dāng)時(shí)最快的遞歸交換算法，同 時(shí)，Ives2是最快的非遞歸交換算法。在 2002 年，Sedgewick 又提出了一個(gè) Heap 遞歸算法 的改進(jìn)版本6，該算法通過(guò)直接排列后三位字符來(lái)加快總體排列產(chǎn)生的速度。 2.2.22.2.2 多重集排列問(wèn)題的研究歷史多重集排列問(wèn)題的研究歷史 與單重集排列相比，多重集排列算法的發(fā)展起步較晚。多重集的排列順序通常有兩種， 字典順序和格雷碼順序。所謂的格雷碼順序，即每相鄰兩個(gè)排列之間只有一個(gè)數(shù)位發(fā)生變化。 F. Ruskey 認(rèn)為，按照格雷碼順序產(chǎn)生多重集排列的算法是在處理多重集排列問(wèn)題中最快的 算法8。James F. Korsh 同 Paul S. Lipschutz 在結(jié)合 Johnsons 22和 Lehmers algorithms 25算 法的基礎(chǔ)上，首次提出了產(chǎn)生多重集排列的 loopness 算法4。在這個(gè)新算法中，多重集的排 列是以鏈表形式產(chǎn)生的，鏈表中的操作都是由指針來(lái)完成，其中包括 O(1)時(shí)間的交換操作。 兩年后，Takaoka 使用數(shù)組改進(jìn)了這個(gè) O(1)時(shí)間的算法5。Vajnovszki54進(jìn)一步提出了一種 基于數(shù)組的少循環(huán)算法。2004 年，James F. Korsh 和 Paul S. LaFollette 提出一種新的 loopness 廈門(mén)大學(xué)本科畢業(yè)論文 9 算法9，與以往基于數(shù)組的算法不同，這個(gè)新算法僅僅需要長(zhǎng)度大小的線性存儲(chǔ)。Takaoka 和 Violich 于 2006 年又提出一種僅僅使用數(shù)組就能在線性空間產(chǎn)生多重集排列的 MULTPERM 算法10，其聲稱(chēng)，MULTPERM 算法比 James F. Korsh 和 Paul S. LaFollettede 的算法9更為簡(jiǎn)單和有效，但是，遺憾的是，他僅僅使用了兩個(gè)非常簡(jiǎn)單的多重集例子： 3,3,3,3,3和2,3,5,2,3 10。另外，盡管不少科學(xué)家對(duì)多重集排列問(wèn)題都給出了精妙的算法， 但這些算法都始終沒(méi)有突破通過(guò)保存和判斷信息來(lái)防止重復(fù)輸出的思維藩籬。 排列問(wèn)題的一個(gè)特點(diǎn)就是輸出規(guī)模受輸入規(guī)模的影響極大。我們假設(shè)計(jì)算機(jī)進(jìn)行一次運(yùn) 算就能給出一個(gè)排列（實(shí)際的算法不可能做到這點(diǎn)） 。對(duì)于一臺(tái)運(yùn)算速度為百萬(wàn)次每秒的計(jì) 算機(jī)， 給出 11 個(gè)元素的集合的所有 11！= 399168 個(gè)排列只需幾秒鐘的時(shí)間，而給出 17 個(gè) 元素的集合的所有 17！= 355687428096000 個(gè)排列則需要幾年。就算是當(dāng)前最快的計(jì)算機(jī)， 其運(yùn)算速度達(dá)到萬(wàn)億次每秒，要計(jì)算出大于 20 個(gè)元素的集合的所有排列在時(shí)間上也顯得不 太可能。在科學(xué)研究中確實(shí)可能遇到較大規(guī)模的排列需求，除了配置高性能的計(jì)算機(jī)之外， 找到一種高性能的排列算法就顯得非常必要。 表 2-1 不同性能計(jì)算機(jī)在各種輸入規(guī)模下進(jìn)行排列所需時(shí)間 N排列的個(gè)數(shù)排列的個(gè)數(shù)百萬(wàn)百萬(wàn)/秒秒十億十億/秒秒萬(wàn)億萬(wàn)億/秒秒 103628800 1139916800幾秒 12479001600幾分鐘 136227020800幾小時(shí)幾秒 1487178291200天分鐘 151307674368000幾周幾分鐘 1620922789888000幾個(gè)月幾小時(shí)幾秒 17355687428096000幾年幾天幾分鐘 186402373705728000幾個(gè)月幾小時(shí) 19121645100408832000幾年幾天 202432902008176640000月 微不足道的時(shí)間微不足道的時(shí)間 漫長(zhǎng)的等待漫長(zhǎng)的等待 廈門(mén)大學(xué)本科畢業(yè)論文 10 2.32.3 歷史上的主要經(jīng)典算法歷史上的主要經(jīng)典算法 在著名的算法大師 Robert Sedgewick 于 1977 年發(fā)表的研究文章中3，他比較了眾多關(guān)于 單重集排列算法，得到了如下結(jié)論， Heap1是最快的遞歸交換算法，同時(shí)， Ives2是最快 的非遞歸交換算法。這兩種算法都是基于交換實(shí)現(xiàn)的。而對(duì)于多重集排列問(wèn)題，F(xiàn). Ruskey 認(rèn)為，按格雷碼順序產(chǎn)生排列的算法是處理此類(lèi)問(wèn)題中最快的算法8。下面，本文將給出以 上三種算法的基本模型和排列產(chǎn)生過(guò)程。 2.3.12.3.1 HeapHeap 遞歸算法遞歸算法 Heap 算法在處理單重集問(wèn)題上是最快的的遞歸算法，它是基于交換實(shí)現(xiàn)的，每次產(chǎn)生 一個(gè)排列時(shí)只交換兩個(gè)位置上的字符的位置，經(jīng)過(guò)遞歸，從而得到所有正確的排列。 定義定義 3 3（P數(shù)組） Pi是 N 位長(zhǎng)度字符串中每一位的字符，i=1,2N。 定義定義 4 4（c數(shù)組） ci是調(diào)用遞歸函數(shù) Permutation( i )時(shí)內(nèi)部控制循環(huán)的計(jì)數(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; 廈門(mén)大學(xué)本科畢業(yè)論文 14 基于格雷碼順序的排列產(chǎn)生結(jié)果如圖 2-3 和 2-4 所示: A B C A C B C A B C B A B C A B A C 圖 2-5 當(dāng) N=3 時(shí)，基于格雷碼的多重集排列算法的排列產(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 當(dāng) N=4 時(shí)，基于格雷碼的多重集排列算法的排列產(chǎn)生圖 廈門(mén)大學(xué)本科畢業(yè)論文 15 第三章第三章 TWDRI 算法的基本模型算法的基本模型 3.13.1 主要流程圖主要流程圖 TWDRI 算法是一種新的快速的全排列產(chǎn)生算法。該算法能同時(shí)解決一般無(wú)重復(fù)輸入的 單重集排列問(wèn)題和重復(fù)輸入的多重集（Multiset）排列問(wèn)題。程序根據(jù)輸入字符串，自動(dòng)選 擇處理單重集排列問(wèn)題的 PurePermutation()函數(shù)，或者處理多重集排列問(wèn)題的 MultisetPermutation()函數(shù)，從而，既滿(mǎn)足了輸入字符串的隨機(jī)性，又達(dá)到了快速處理兩種不 同集合的排列問(wèn)題。 圖 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)生排列的過(guò)程算法產(chǎn)生排列的過(guò)程 為了形象地表示出算法 TWDRI 產(chǎn)生排列的過(guò)程，我們通過(guò)以下兩個(gè)例子來(lái)具體說(shuō)明。 廈門(mén)大學(xué)本科畢業(yè)論文 16 圖 3-2，圖 3-3 分別說(shuō)明了當(dāng)輸入是多重集 A,X,X 和1,2,3,3時(shí)排列產(chǎn)生的過(guò)程。其中， 線條上的數(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)生過(guò)程 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)生過(guò)程 3.33.3 算法時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度 算法的計(jì)算時(shí)間 T(n)滿(mǎn)足： （3- 12 3 (1)*(3) ( ) (3) nT nCnCn T n Cn 廈門(mén)大學(xué)本科畢業(yè)論文 17 1） 輸入規(guī)模為 n3 的問(wèn)題可由 n 個(gè)輸入規(guī)模為 n-1 的子問(wèn)題構(gòu)成。是對(duì)子問(wèn)題 12 *CnC 結(jié)果進(jìn)行分解和合并的花費(fèi)，其中、為常數(shù)。當(dāng) n=3 求解問(wèn)題的花費(fèi)為，為常數(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 的遞歸樹(shù) 12 ( )(1)*T nnT nCnC 從樹(shù)的根結(jié)點(diǎn)開(kāi)始,根有 n 個(gè)分支，第二層的每個(gè)節(jié)點(diǎn)有 n-1 個(gè)分支，一直到倒數(shù)第二 層的每個(gè)節(jié)點(diǎn)有 2 個(gè)分支，共 n+1 層。樹(shù)的第一層有 1 個(gè)節(jié)點(diǎn)，第二層有 n 個(gè)節(jié)點(diǎn)，以下各 層依次節(jié)點(diǎn)數(shù)為 n(n-1)、n(n-1)(n-2),最后一層為 n!個(gè)。 接下來(lái)分析在每層的花銷(xiāo)。TWDRI 算法的最大特點(diǎn)在于，隨著遞歸層數(shù)的增加，子問(wèn) 題的取值空間不斷縮小，因此，在每個(gè)節(jié)點(diǎn)上對(duì)子問(wèn)題的分割和合并的花費(fèi)也從第一層的 到最后一層的不斷下降。 12 *CnC 12 CC 本文的算法無(wú)需到達(dá)樹(shù)結(jié)構(gòu)的最后一層，而在倒數(shù)第三層時(shí)便能輸出排列。因?yàn)樵谶f歸 樹(shù)中一層節(jié)點(diǎn)的數(shù)目與其以上所有祖先節(jié)點(diǎn)的數(shù)目之和相近，所以最低兩層的排除能帶來(lái)性 能上的巨大提高。 總的時(shí)間花費(fèi)有： 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 廈門(mén)大學(xué)本科畢業(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） 對(duì)于輸入元素個(gè)數(shù)為 n 的全排列問(wèn)題，其輸出的規(guī)模為 n!。因此時(shí)間復(fù)雜度中的 n！是 由問(wèn)題本身固有的內(nèi)在特點(diǎn)所決定的。本文算法的時(shí)間復(fù)雜度最終可以表示為 C*n!(C 為常 數(shù))，即從漸進(jìn)意義上已達(dá)到排列問(wèn)題時(shí)間復(fù)雜度的理論下界。 在大多數(shù)時(shí)間復(fù)雜度的分析中，常數(shù) C 都是對(duì)程序中語(yǔ)句行數(shù)的計(jì)算。為了進(jìn)行較為 精確的分析,我們采用了和 Ives 相同的方法，即計(jì)算程序中的賦值、數(shù)值運(yùn)算、比較和下標(biāo) 引用的使用次數(shù)。 3.43.4 算法的通用性算法的通用性和創(chuàng)新性和創(chuàng)新性 定義定義 9 9（Mappings數(shù)組） 對(duì)于長(zhǎng)度為 N，有 k 個(gè)不同字符，每個(gè)字符個(gè)數(shù)分別為 n0, n1, , nk-1的字符多重集，我們引進(jìn)數(shù)組 Mappings來(lái)映射 k 個(gè)不同字符。k 此時(shí)為 Mappings 數(shù)組的長(zhǎng)度。Mappingsi = ni所對(duì)應(yīng)的不同字符，當(dāng) i = 0, 1, 2, , k-1 時(shí)。 例如，當(dāng)輸入字符串為“0112”時(shí)，我們可以得到： N = 4, k =3, n0 =1, n1 =2, n2 = 1; Mappings0 = 0, Mappings1 = 1, Mappings2 = 2。 同理，當(dāng)輸入字符串為“abbc”時(shí)，我們可以得到： 廈門(mén)大學(xué)本科畢業(yè)論文 19 N = 4, k =3, n0 =1, n1 =2, n2 = 1; Mappings0 = a, Mappings1 = b, Mappings2 = c。 顯然，對(duì)于以上兩個(gè)例子，雖然輸入不同，但是，它們映射到了相同的數(shù)字多重集 0,1,1,2。 與已有算法不同，TWDRI 采用了 Mappings數(shù)組，將各個(gè)不同輸入字符一對(duì)一映射到 連續(xù)的自然數(shù)數(shù)組，排列過(guò)程中僅僅對(duì)此自然數(shù)組進(jìn)行操作。由于最后排列的產(chǎn)生是根據(jù)自 然數(shù)與字符對(duì)應(yīng)關(guān)系得到的，這樣，既解決了傳統(tǒng)的多重集問(wèn)題，又滿(mǎn)足了一般字符的隨機(jī) 輸入，具有廣泛的通用性。 更為難得可貴的是，TWDRI 算法沒(méi)有進(jìn)行換位，也沒(méi)有按照格雷碼順序產(chǎn)生排列，在 速度上就超越了原有已知的解決相同問(wèn)題的最快算法，從而，打破了傳統(tǒng)解決單重集排列問(wèn) 題中最快算法都是基于換位的一般看法，也打破了多重集問(wèn)題中最快的排列產(chǎn)生方法是基于 格雷碼順序的論斷。這對(duì)全排列算法的研究來(lái)說(shuō)，無(wú)疑是個(gè)巨大的突破，具有歷史創(chuàng)新性。 廈門(mén)大學(xué)本科畢業(yè)論文 20 第四章第四章 模擬比較模擬比較 4.14.1 多重集排列的平均時(shí)間計(jì)算模型多重集排列的平均時(shí)間計(jì)算模型 下面我們將首先給出基于隨機(jī)輸入的平均時(shí)間計(jì)算模型，并進(jìn)行推導(dǎo)，從而得出多重集 排列的平均時(shí)間計(jì)算公式。 4.1.14.1.1 基于隨機(jī)輸入的平均時(shí)間計(jì)算模型基于隨機(jī)輸入的平均時(shí)間計(jì)算模型 為了全面客觀的比較各個(gè)多重集算法的性能，我們需要對(duì)隨機(jī)輸入長(zhǎng)度為 N 的字符串 的所有情況進(jìn)行測(cè)試。一個(gè)輸入的產(chǎn)生可以看成是從 N 個(gè)字符中每次抽取 1 個(gè)字符填滿(mǎn) N 個(gè)有序格子。每個(gè)格子都有 N 種字符可選，所有共有 N N種輸入情況。 然而我們不必測(cè)試所有的 N N種輸入，因?yàn)槠渲杏行┹斎氲呐帕袝r(shí)間是相同的。以長(zhǎng)度 4(N4)為例，顯然輸入“AAAA”和“BBBB”進(jìn)行排列時(shí)間相同，輸入“AABB”, “CCDD”和“BCBC”的排列時(shí)間也是一樣的。這樣我們就可以對(duì)所有的輸入情況進(jìn)行分 類(lèi)，把那些具有相同排列時(shí)間的輸入劃分到一類(lèi)中，得到 D 種分類(lèi)。最后，我們只需測(cè)試 每類(lèi)中的一個(gè)輸入的排列時(shí)間 td，再將時(shí)間 td乘以該類(lèi)輸入的出現(xiàn)概率，求和，就可以得到 該類(lèi)所有輸入情況的平均排列時(shí)間 T，也即： （4-1） 1 0 ( )* D d d Tprobability of group dt 4.1.24.1.2 計(jì)算模型的推導(dǎo)過(guò)程計(jì)算模型的推導(dǎo)過(guò)程 下面將利用數(shù)論中整數(shù)分拆（或稱(chēng)整數(shù)剖分）的理論來(lái)介紹 N N種輸入的分類(lèi)過(guò)程。 事實(shí)上，我們可以把分類(lèi)可以抽象為對(duì)正整數(shù) N 的分拆。正整數(shù) N 的分拆是指，把 N 表示為一個(gè)或多個(gè)正整數(shù)的無(wú)序和，其中，每一個(gè)無(wú)序和就是 N 的一個(gè)分拆。由于分拆成 的若干個(gè)正整數(shù)的順序是不重要的，因此我們總可以排列這些正整數(shù)，使得它們的順序從最 大到最小。例如正整數(shù) 4 對(duì)應(yīng)的分拆為 4=4，4=3+1，4=2+2，4=2+1+1，4=1+1+1+1。 簡(jiǎn)而言之，N 的一個(gè)分拆可以寫(xiě)成： 廈門(mén)大學(xué)本科畢業(yè)論文 21 （4- 21 2 1 i aaa iiN （1） 2） (這個(gè)表達(dá)式是純符號(hào)性的；它的項(xiàng)既不是指數(shù)式，表達(dá)式也不是一個(gè)乘積)。 其中為非負(fù)整數(shù)，該數(shù)等于值為 i 的正整數(shù)的個(gè)數(shù)。當(dāng)被寫(xiě)成式（4-2）的形式時(shí)，若 i a 0，則項(xiàng)通常被省略，使用 這個(gè)記號(hào)，4 的分拆為：41，3111，22，2112，14。 i a i a i 的每種形式對(duì)應(yīng)一種分類(lèi)，則正整數(shù) 4 的分拆總共有 5 類(lèi)，具體如下表 21 2 1 i aaa i 4-1 所示： 表 4-1 正整數(shù) 4 的分拆 d 字符串舉例字符串舉例 k= 1 n i i a 141AAAA1 23111AAAB2 322AABB2 42112AABC3 514ABCD4 顯然，應(yīng)用這種分拆的分類(lèi)思想，我們可以得到，為多重集問(wèn)題中互不相同的字符 1 n i i a 的個(gè)數(shù) k，根據(jù)定義 2，每種分類(lèi)中的各個(gè)字符的重復(fù)次數(shù) n0, n1, , nk-1也能輕松得出，即 中每個(gè)不為 0 的的下標(biāo)項(xiàng) i，也因此，此時(shí) n0 n1nk-1 21 2 1 i aaa iiN （1） i a 至此，為了求得每種分類(lèi)的出現(xiàn)概率，我們還需要計(jì)算每種分類(lèi)包含的輸入情況的個(gè)數(shù)。 還是以長(zhǎng)度 4 為例，不失一般性，假設(shè)組成輸入字符串的字符集合為A,B,C,D，每種分類(lèi) 中組成該類(lèi)一個(gè)輸入的不同字符個(gè)數(shù)為 k，而從字符集合中選取 k 個(gè)字符有種選法。表 4- k N C 1 第 4 行 k=1+2=3，所以共有=4 種選擇：ABC，ABD，ACD，BCD；對(duì)于一種選擇如 3 4 C ABC 我們還要考慮哪個(gè)字符重復(fù)出現(xiàn) 2 次：A 出現(xiàn) 2 次得到 AABC，B 出現(xiàn) 2 次得到 BBAC，C 出現(xiàn) 2 次得到 CCAB，因此要對(duì)每種選擇的字符進(jìn)行排列，有排列個(gè)數(shù) =3；當(dāng) A 出現(xiàn) 2 次時(shí)，AABC，BAAC 和 BACA 也是不同的，排列個(gè) 1 !/ N i kai 3!/(1!*2!) 廈門(mén)大學(xué)本科畢業(yè)論文 22 數(shù)為=12。所以，當(dāng) N=4，k=3，分拆 2112所對(duì)應(yīng)的分類(lèi)總 11 !/( !) a N i jk Ni 4!/(2!*1!*1!) 共有 4*3*12 種輸入情況，其在所有 44種隨機(jī)輸入中所占的概率為 4*3*12/44。 所以，每個(gè)分類(lèi)中所有輸入情況的出現(xiàn)概率為： （4- 111 (!/!)(!/( !)/ d a NN i kn Nd ikj probability of group dCkaNiN i 3） 4.1.34.1.3 平均時(shí)間計(jì)算公式平均時(shí)間計(jì)算公式 為了方便應(yīng)用與理解，我們根據(jù)以上推導(dǎo)，總結(jié)如下： 假定一個(gè)輸入中有 k 個(gè)不同的字符，每個(gè)字符的個(gè)數(shù)分別為 n0, n1, , nk-1，顯然，N = n0 + n1 + nk-1。不失一般性，我們假定 D 為 n0, n1, , nk-1的不同拆分?jǐn)?shù)，其中 n0 n1nk-1， 并且 N = n0 + n1 + nk-1。此時(shí)，對(duì)于長(zhǎng)度為 N 的字符串的所有可能 N N種 輸入，就分成了 D 種不同的類(lèi)別。我們用來(lái)表示 D 種分類(lèi)中的不 ,0,1,2,1 ,., d dddd k nnnn 同組合，其中，d = 0, 1, , D-1.對(duì)于每一種分類(lèi)，它們有相同的排列時(shí)間，即 td，其中，d = 0, 1, , D-1。 對(duì)于一個(gè)固定的 d 值，我們用 rd來(lái)表示中不同數(shù)字的個(gè)數(shù)， ,0,1,2,1 ,., d dddd k nnnn 用來(lái)分別記錄每個(gè) rd值的個(gè)數(shù)。表 4-2 顯示了當(dāng) N=4 時(shí)N N種輸入中 ,0,1,1 ,., d ddd r mmm 分別帶有一個(gè)代表性例子的 5 種分類(lèi)。 表 4-2 當(dāng)N=4 的N N種輸入的 5 種分類(lèi) 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 對(duì)于 N N種可能輸入的平均排列時(shí)間為： 1 0( ) D d d probability of group d t 11 1 , 000 (!/!)(!/!)/ dd d rk D kN Ndd jd jd djj CkmNntN 廈門(mén)大學(xué)本科畢業(yè)論文 23 （4- 1 1 1 , 000 (!/)()/!)(!)( ! d d k r D d kN dd Nd jd j djj NCnm Nkt 4） 例如，當(dāng)N = 4（參見(jiàn)表4-2） ，隨機(jī)輸入長(zhǎng)度為 4 的字符串的平均排列時(shí)間為： 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 模擬比較結(jié)果模擬比較結(jié)果 借鑒以往大型模擬比較的經(jīng)驗(yàn)56，我們把 TWDRI 算法同 11 種已知最快或最新的算法 進(jìn)行模擬比較。為保證比較的的科學(xué)性、準(zhǔn)確性和公平性，所有的算法都用遵循 ANSI C 標(biāo) 準(zhǔn)的 C 語(yǔ)言實(shí)現(xiàn)，并且運(yùn)行在相同配置的計(jì)算機(jī)上（Pentium 4，CPU 2.93 GHz，1 GB 內(nèi)存） 。 從通用性出發(fā)，我們模擬測(cè)試選擇的字符串從字符 0-9 和 a-j 中選出。例如，當(dāng)模擬單 重集算法時(shí)，如果 N=5，模擬測(cè)試的字符串為 “01234；如果 N=17，模擬測(cè)試的字符串則 為“0123456789abcdefg”。 以下是縮寫(xiě)說(shuō)明: Heap63: 遞歸交換算法1 Heap63: 非遞歸交換算法1 Ives 76:非遞歸交換算法2 JT: loopless Johnson-Trotter 算法(算法 3b)3 JTLLC03: Jeeve Technologies LLC 算法7 KL97: Korsh 和 Lipschutz 常數(shù)時(shí)間算法4 KL04: Korsh 和 LaFollette 基于數(shù)組的少循環(huán)算法9 Ruskey 03: Ruskey 算法53 Sedgewick02: Sedgewick 算法6 廈門(mén)大學(xué)本科畢業(yè)論文 24 Takaoka99: Takaoka 的 O(1)算法5 TV06: Takaoka 和 Violich 的算法10 4.2.14.2.1 多重集算法的時(shí)間和內(nèi)存開(kāi)銷(xiāo)比較多重集算法的時(shí)間和內(nèi)存開(kāi)銷(xiāo)比較 表 4-3 和圖 4-1 說(shuō)明 TWDRI 算法在處理多重集問(wèn)題中，速度至少是其它 5 種算法中任 何一種的 3 倍。表 4-4 則說(shuō)明，相對(duì)其它算法而言，TWDRI 算法的內(nèi)存開(kāi)銷(xiāo)是比較小的。 因此，顯而易見(jiàn)的，同各種多重集排列算法相比，TWDRI 算法表現(xiàn)出相當(dāng)優(yōu)秀的時(shí)間和空 間性能。 表 4-3 多重集排列算法的平均時(shí)間比較 (單位：毫秒) 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 多重集全排列算法的平均時(shí)間比較 表 4-4 多重集全排列算法內(nèi)存的峰值平均值比較 (單位：KB) 廈門(mén)大學(xué)本科畢業(yè)論文 25 NTWDRI KL97KL04Ruskey03Takaoka 99 TV06 11768768813813780780728728788788864864 12772772832832788788732732792792868868 13776776859859792792736736800800876876 14772772897897796796740740812812888888 15784784941941804804748748824824896896 16800800752752 4.2.24.2.2 多重集算法在非重復(fù)輸入的情況下的時(shí)間比較多重集算法在非重復(fù)輸入的情況下的時(shí)間比較 表 4-5 和圖 4-2 說(shuō)明，在非重復(fù)輸入的情況下，TWDRI 算法的速度是其它 5 種多重集 算法中最快算法的 9 倍。 表 4-5 多重集全排列算法在無(wú)重復(fù)輸入下的時(shí)間比較 (單位：毫秒) NTWDRIKL97KL04Ruskey 03Takaoka 99TV06 10017223463547203 11791,9842,7197666,0162,125 1296923,42234,3758,56572,23425,985 1312,438290,375459,907118,229965,76533