多重集的全排列算法研究-毕业论文.doc

1、厦门大学本科毕业论文 1 本科毕业论文 (科研训练、毕业设计 ) 题 目： 多重集 的全排列算法研究 姓 名： 学 院：软件学院 系： 专 业：软件工程 年 级： 学 号： 指导教师（校内）： 职称： 年 月 厦门大学本科毕业论文 2 多重集全排列算法研究 摘要 排列产生算法的研究在计算机发明之前已被人们所研究，其历史甚至可以追溯到三百年之久。本文提出一种新的全排列产生算法 TWDRI。该算法能同时解决一般的无重复输入的单集问题和重复输入的多重集 (multiset)问题。 TWDRI 突破了以往只有采用换位思想才能达到最快速度的传统思想的束缚，以自身独特的数据结构设计为基石，充分利用递归方式

2、的优势，取得远优于其他同类算法的速度和内存损耗。此外，不同于大多数排列产生算法只能处理数值的特性，本算法适用于各种不同字符的输入情况，具有通用性。为了能客观评价现有各种排列算法的性能，本文提出了一种新的性能计算模型，可以精确的测出各类算法的平均运行时间。在此基础上，我们进行了大量的模拟，测试了从 10 位到 17 位的输入情况，与已知最快和最近的算法进行比较 12345678910， TWDRI 的速度处于领先水平。 关键词 多重集 全 排列 算法 厦门大学本科毕业论文 3 A Research into Multiset Permutation Algorithm Abstract TWDR

3、I algorithm, the fastest new permutation technique for multiset permutations was proposed in this paper. A multiset is a set for which repeated elements are considered. We consider any character string of length N as a multiset, which has k different characters, each has count n0, n1, , nk-1, respec

4、tively. 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

5、. 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

6、known and/or well-known algorithms 12345678910 in detail. The comparisons show our algorithm is three times faster than the fastest of them for multiset permutations and 1.3 times faster than the fastest of them for pure permutations. Our memory consumption is under 800Kb, which is very low for toda

7、ys 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 Algoirthm 厦门大学本科毕业论文 4 目录 第一章 引言 . 6 第二章 研究背景 . 7 2.1 问题定义 . 7 2.2 主要算法 . 7 2.2.1 字典序算法 . 7 2.2.2 Heap 算法 .

8、 8 2.2.3 Ives 算法 . 9 2.2.4 Johnson and Trotter 算法 . 11 2.2.5 Constant Time 算法 . 13 2.3 应用 . 14 第三章 TWDRI .15 3.1 算法流程图 . 15 3.2 算法思想 . 15 3.3 例子 . 16 3.4 时间复杂度分析 . 16 第四章 测试模型 .19 第五章 测试结果 .21 5.1 TWDRI 算法和其它单集排列算法的速度和内存比较 . 21 5.2 多重集算法的时间和内存开销比较 . 22 5.3 多重集算法在非重复输入的情况下的时间和内存开销比较 . 23 5.4 TWDRI 算法

9、与其它多重集排列算法的比较趋势分析 . 24 第六章 结论 .26 致谢语 .27 参考文献 .28 厦门大学本科毕业论文 5 Contents Chapter 1 Introduction . 6 Chapter 2 Background . 7 2.1 Definition . 7 2.2 Classic algorithms . 7 2.2.1 Lexicographic Algorithm . 7 2.2.2 Heap Algorithm . 8 2.2.3 Ives Algorithm . 9 2.2.4 Johnson and Trotter Algorithm . 11 2.2.

10、5 Constant Time Algorithm . 13 2.3 Implementation. 14 Chapter 3 TWDRI .15 3.1 Main Flowchart . 15 3.2 Main Idea. 15 3.3 Example. 16 3.4 Time Complexity Analysis . 16 Chapter 4 Testing Model .19 Chapter 5 Test Result .21 5.1 Pureset Permutation Algorithms Comparisions . 21 5.2 Multiset Permutation Al

11、gorithms Comparisions. 22 5.3 Multiset Permutation Algorithms Comparisions with Distinct Inputs . 23 5.4 Trends Analysis . 24 Chapter 6 Conclusion.26 Acknowledgements .27 References.28 厦门大学本科毕业论文 6 第一章 引言 万花筒般美丽繁华的万千世界之所以异彩纷呈，并不因其本质有何等的错综复杂。洗尽铅华后，人们发现纷繁的背后往往只是些 看似平凡无奇的事物的排列组合，就好像简单几个小纸片和小镜片的巧妙搭配就能焕发

12、出万花筒炫目的五光十色。 在科学界，排列组合问题更是与科学家们如影相伴。爱迪生 经过两千 多次的各种材料的排列组合才找到发明电灯的方案；袁隆平也是经历了无数次的组合排列实验才找到了优质的杂交水稻。排列组合广泛的应用范围 和 重 大 的 科 学 意 义 促 成 了 研 究 者 们 数 百 年 来 孜 孜 不 倦 的 追 索 和 探 求1234567891011121314151617181920212223242526272829303132333 4353637383940414243444546474849505152535455。 溯其根源，可以回到那遥远的 十六世纪五十年代 ， 教堂中的

13、牧师计算几口大钟不同的撞击顺序来产生各式的音乐效果。 早在 1960 年就有这一领域算法的总结性文章出现 13。 Robert Sedgewick 在 1977 年对众多排列产生方法中的经典算法做了分析和比较 3，具有代表性的有M. B. Wells在 1960 年发表的 Recursive methods15， 1965 年 J. Boothroyd 对其进行了改进 2628；1962 年 S. M. Johnson21和 H. F. Trotter20分别独立提出的 Adjacent exchanges 是一重大突破 ； Factorial counting 算法是 Johnson-Tro

14、tter 算法的另一种实现 ； 同样是在 Johnson-Trotter 算法的基础上 G. Ehrlich3334引进了减少内部循环的思想得到 “Loopless” algorithm，这一算法被 N. Dershowitz进一步的优化 ； 其它还有 F. M. Ives的 iterative method 2； C. Tompkins和 L. J. Paige的 Nested cycling12, Peck 和 Schrack 给出了这一算法的 ALGOL 程序 17，还有许多研究人员对 这 一 算 法 进 行 改 进 13142432363739 ； 比 较 有 影 响 的 算 法 还

15、有 Lexicographic algorithms1116181922252930与 Random permutations1323242731。 以上这些算法仅能解决无重复输入的问题。 多重集 (multiset)输入是一个相对较难的问题，不少研究者一直在寻求一个高性能的算法 45384054。在求解多重集排列问题时传统算法为防止重复输出而保存大量纪录信息，许多研究人员投入经历简化纪录信息的保存和判断验证过程，也产生了许多精妙的算法。但这些算法都始终没有突破通过保存和判断信息来防止重复输出的思维 枷锁 。 厦门大学本科毕业论文 7 第二章 研究背景 2.1 问题定义 定义 1 （ 单集 ）

16、 对于一个长度为 N 的字符串来说，如果它有 k 个不同的字符，每个字符重复出现的次数均为 1，即 N=k, 我们称这样的输入为单集，其排 列称为单集全排列。 定义 2 （多重集） 对于一个长度为 N 的字符串来说，如果它有 k 个不同的字符，每个字符重复出现的次数分别为： n0, n1, , nk-1（这些数不全为 1） 。 我们称这样的输入为多重集 , 它们的全排列问题也因此被称为多重集全排列问题。 定理 1 （多重集长度 特性 ） 对于一个长度为 N 的多重集，它有 k 个不同的字符，每个字符重复出现的次数分别为： n0, n1, , nk-1。 N = n0 + n1 + nk-1。

17、2.2 主要算法 单集全排列问题在 1977 年 Sedgewick 的综述性论文 3后几乎很难有重大的突破， 最为人们所熟知的字典序法， 最优秀最经典的是迭代算法 Ives2。在递归算法领域中则以 Heap1一支独秀。另外一篇具有奠基意义的是 Johnson and Trotter2021算法 ，曾引发了一场研究Loopless 算法的热潮 9103346485154。 相比 单集 ，多重集的研究则有更大的发展空间。Constant Time4算法是这方面的代表。 2.2.1 字典序 算法 字典序是排列算法中最经典的算法，在各种排列场合下被广泛引用。 字典序排列算 法的优点是简单易懂，规律性

18、强。但要实现从一个排列得到它的下一个排列通常需要较多的操作。 以集合 A、 B、 C为例，按字典序生成的全排列是： ABC,ACB,BAC,CAB,CBA。字典序法就是预先定义需要排列的 k 个元素的次序 n1,n2.nink。给出两个排列 P1 和 P2，如果P1 和 P2 的前 i 1 个元素都相同， P1 的第 i 个元素为 na， P2 的第 i 个元素为 nb， a 2: i:=i-1 repeat; process; loop if ci 1; Do IF ci (n-i) THEN tem = Pci-1; Pci-1 = Pci; Pci = tem; ci = ci + 1; i = 1; OutputPerm; ELSE tem = Pi; Pi = Pn-i+1; Pn-i+1 = tem; ci = i; IF Pn-i+1 = = Qn-i+1 THEN i = i + 1; ELSE i = 1; ENDIF ENDIF WHILE i (n-i+1)