1、 本科毕业论文 (科研训练、毕业设计 ) 题 目： 多重集全排列算法 的 研究 模拟比较与汇编分析 姓 名： 学 院：软件学院 系： 软件工程 专 业：软件工程 年 级： 学 号： 指导教师 ： 职称： 年 月I 摘 要 全排列问题是组合数学中的基础问题，对它的研究已经有几个世纪的历史了，几百年来产生了很多种类的全排列算 法。但是，大于 25 的全排 列对于我们来 说规模仍过于庞大 ， 因此我们需要更快的算法 。本文研究了众多全排列的经典算法，对它们进行了分析和总 结， 在此基础上提出了 TWDRI 算法 ，它突破了以往只有采用换位思想才能达到最快速度的传统思想的束缚，以自身独特的数据结构设计
2、为基石，充分利用递归方式的优势，取得远优于其他同类算法的速度和内存损耗。此外， 不同于大多数排列产生算法只能 处理数值的特性，本算法适用于各种不同字符的输入情况，具有通用性 。 本文 设计了平均时间测试模型， 经过大量的时间 测试和模拟比较，得出 TWDRI 是目前速度最快算法 的结论。为了进一步验证 该结论 ，我们选择在汇编语言的环境下进行数学分析，力求通过数学公式的比较证明 TWDRI 算法的优越性。最后，本文还提出了 该领域 未来的 一些 研究方向。 关键 词 ： 全 排列 汇编 数学模型 多重集 II Abstract Permutation is the basic problem
3、in combinatorics， and the research work has been carried on for hundreds of years, which produced many types of methods to do the permutation calculation. However, the permutation of the number which is larger than 25 is still beyond us. As a result, we need a swifter algorithm. This thesis does the
4、 research on these classic algorithms, analyzes and summaries them, on the basis of which brings out the TWDRI algorithms. This method broke the traditional limits that the largest speed can only be achieved by using the exchange methods. It is based on the special design of data structure and makes
5、 the best use of the advantages of recursion, thats how it obtains the speed and memory cost which can hardly be achieved by its counterparts. Moreover, different from the traits of most permutations that the algorithms produced can only deal with data, this calculation is quite universal, for it su
6、its different entering situations of all kinds of string. The average time test model is designed in this thesis and we can conclude that TWDGI is the fastest algorithm in the present world after a large amount of time tests and simulation comparisons have been practiced. To further check this concl
7、usion, we decide to do the mathematical analysis in the environment of compilation language, trying to prove the superiority of TWDRI by the comparisons of mathematical formulas. In the end, this thesis also provides some hints about the future research direction in this field. Key words: Permutatio
8、n ; Assembly ; Mathematics Model ; MultisetIII 目录 第一章 绪论 . 1 1.1 研究背景及意义 . 1 1.2 基本概念 . 2 1.3 本文主要内容 . 4 1.4 本文组织结构 . 4 第二章 经典算法 . 5 2.1 基于相邻交换的算法 . 5 2.1.1 简介 . 5 2.1.2 代表算法 . 6 2.2 基于递归的算法 . 7 2.2.1 简介 . 8 2.2.2 代表算法 . 8 2.3 基于迭代的算法 . 9 2.3.1 简介 . 10 2.3.2 代表算法 . 10 2.4 字典序类算法 . 11 2.4.1 简介 . 11 2
9、.4.2 代表算法 . 12 2.5 其他 . 12 2.5.1 Loopless 算法 . 12 2.5.2 基于 GrayCode 序的算法 . 12 2.5.3 随机排列 . 13 第三章 TWDRI 算法与模拟比较 . 14 3.1 简介 . 14 3.2 平均时间测试模型 . 15 3.2.1 平均时间测试程序 . 18 3.3 模拟比较 . 19 3.3.1 Knuth 算法 . 19 IV 3.3.2 模拟比较环境 . 20 3.3.3 多重集排列算法的时间和内存比较 . 21 3.3.4 单集排列算法的时间和内存比较 . 23 3.3.5 TWDRI 算法与其它多重集排列算法的
10、比较趋势分析 . 25 第四章 汇编分析 . 26 4.1 分析工具 MIX . 26 4.2 性能分析 . 27 第五章 总结与展望 . 35 5.1 总结 . 35 5.1.1 排列的应用 . 35 5.1.2 总结 . 35 5.2 未来的研究方向 . 36 5.2.1 Hybrid algorithm . 36 5.2.2 多线程并行算法 . 39 致谢语 . 42 参考文献 . 43 附录 . 47 V Contents Chapter 1 Introduction. 1 1.1 Background . 1 1.2 Basic Concept . 2 1.3 Main Conten
11、t. 4 1.4 Structure of This Thesis . 4 Chapter 2 Classical Algorithm . 5 2.1 Algorithm Based On The Adjacent Exchange . 5 2.1.1 Introduction . 5 2.1.2 Representative Algorithm . 6 2.2 Algorithm Based On Recursive . 7 2.2.1 Introduction . 8 2.2.2 Representative Algorithm . 8 2.3 Algorithm Based On Ite
12、ration . 9 2.3.1 Introduction . 10 2.3.2 Representative Algorithm . 10 2.4 Lexicographic Algorithm . 11 2.4.1 Introduction . 11 2.4.2 Representative Algorithm . 12 2.5 Others . 12 2.5.1 Loopless Algorithm. 12 2.5.2 Algorithm Based On GrayCode . 12 2.5.3 Random Algorithm. 13 Chapter 3 TWDRI Algorithm
13、 and Simulation Comparison. 14 3.1 Intriduction. 14 3.2 The Average Time Test Model . 15 3.2.1 Test Program for Average Time . 18 3.3 Simulation Comparsion . 19 3.3.1 Knuth Algorithm . 19 3.3.2 Simulation Comparsion Environment. 20 VI 3.3.3 Average Time and Memory Consumption of Multiset Permutation
14、 . 21 3.3.4 Time and Memory Consumption of Pure Permutation . 23 3.3.5 Speed Ratios of TWDRI Algorithm to Other Algorithms. 25 Chapter 4 Assemmbly Analysis . 26 4.1 Analysis ToolMIX . 26 4.2 Performance Analysis . 27 Chapter 5 Conclusions and Future Work . 35 5.1 Conclusions . 35 5.1.1 Application.
15、35 5.1.2 Conclusions . 35 5.2 Future Work . 36 5.2.1 Hybrid algorithm. 36 5.2.2 Multi-threads Parallel Algorithm . 39 Acknowledgments . 42 References . 43 Appendix . 47 厦门大学本科毕业论文 1 第一章 绪论 本章将从课题研究背景及意义，论文主要内容，本文组织结构 等 方面对论文做总体上的介绍。 1.1 研究背 景及意义 排列和组合一直是组合数学 研究的重点，全排列广泛 地应用在各种复杂的软件中，尽管数学概念简单，但程序实现并不
16、容易， 排列中包含着多种形式的数据 结构。排 列算法的研究在计算机发明之前已经开始，其历史甚至可以追溯到 14 世纪的印度，当时已经产生了解决排列问题的算法。 十六世纪五十年代 ，教堂中的牧 师 曾 计算 过 几口大钟 如何用 不同的撞击顺序来产生各式的音乐效果，这也是排列问题历史上的一个经典事件。 几个世纪以来，产生了众多的排列算法 1-50。 算法大师 Donald E. Knuth 在其经典著作计算机程序设计艺术一书 中写道：“事实上，排列 (permutations)问题在计算机领域非常重要。 Vaughan Pratt 提议直接把它叫做 perms。如果Pratt 的建议得以实施，那
17、么计算机教科书的厚度将变得薄一些 (相应书的价格也会便宜一点 )”1。 由此可见排列在计算机领域出现的频率之高。正是因为排列问题如此重要，所以一直以来有众多的研究人员致力于该问题的解决。进入 20 世纪，排列问题的研究取得了突飞猛进 的进 展 ， 不断涌现出一些有代表性的算法。普林斯顿大学计算机系算法大师 Robert Sedgewick在 1977 年对众多排列产生 方法中的经典算法做了分析和比较 2，这是一篇非常经典 的 极 具参考价值的文章， Robert Sedgewick 倾注了大量的心血，阅读了大量的相关资料，对 1977 年以前出现的关于排列问题的论文进行了非常完整的总结。 M.
18、 B. Wells 在 1961 年第一次提出了 Recursive Method3， 此后 递归 算法逐渐成为排列算法的一大类别。 1962 年 S. M. Johnson和 H. F. Trotter 提出的 Adjacent exchanges 算法 4，而这也称为排列算法的一个类别。在Johnson-Trotter 算法的基础上 G. Ehrlich 引进了减少内部循环的思想得到 Loopless 算法 5， 之后，随着 发展 的继续推进 ， Loopless 也成 为排列算法中一个相当重要的类别。此外，基于迭代 6，格雷编码 7，以及树形结构 8等的排列算法在 20 世纪的后几十年里
19、逐渐出现 ， 最近几十年来，各个类型的排列算法大量涌现。 2006 年算法大师 Donald E. Knuth 在其巨著计算机程序设计艺术 1第四卷第二册中专门对生成排列的多种算法进行了详细的概括与分析。 之所以出现这么多排列算法，是因为 排列问题的瓶颈仍 然 没法突破 ，人们 一直 试 图找出厦门大学本科毕业论文 2 速度 更快 ， 性能更高的算法，但是其根本问 题 规模庞大 ， 还是没有实质 性的 解决 办法 。我 们假设计算机进行一次运算就能给出一个排列 (实际的算法不可能做到这点 )。对于一台运算速度为百万次每秒的计算机， 给出 11 个元素的集合的所有 11！ = 399168 个排
20、列只需几秒钟的时间，而给出 17 个元素的集合的所有 17！ = 355687428096000 个排列则需要几年。就算是当前最快的计算机，其运算速 度 能 达到 万亿次每秒，要计算出大于 20 个元素的集合的所有排列在时间上也显得不太可能， 详见表 1-1。 表 1-1 不同性能计算机在各种输入规模下进行排列所需的时间 排列问题是一个经典的数学 问题，它有着悠久的历史，也有着广泛的实际应用，比如说在密码学领域对输入的一些数字或字符产生其对应的密码；在生物医学领域 DNA 序列的排列等等。 在 DNA 分析、加密解密、电路设计、运筹研究、统计计算、化学 等 领域中你都可以看到排列与组合的应用。
21、因此，研究字符串的全排列问题有很大的 实际 意义。 1.2 基本概念 定义 1 (排列 ): 组合数学的基本概念，从有限个元素中取出全部或一部分按照一定的 顺序排成的一个系列。例如 3 个数码 1， 2， 3 全部取出可以 作成 6 个不同的排列： 123， 132， 213，231， 312， 321。在组合数学中， 常 要研究由指定的一组元素中每次取出一定数量的元素来作排列 ，一共能作多少个不同的排列，用符号 mnp 表示从 n个不同的元素中任意取出 m 个元素厦门大学本科毕业论文 3 所作的不同排列的总数，那么有公式 ( 1 ) ( 2 ) .( 1 )nnp n n n n m ，称为
22、排列数公式。当 m n 时，称为全排列，全排列数公式为 ( 1 ) ( 2 ) .2 * 1 !nnp n n n n 。记号 n！表示从 1 到 n这 n个自然数的连乘积，称为阶乘。 定义 2 (单集排列 ): 给定的字符串不包含重复字母，将其进行全排列，把其 所有可能的全排列 准确 无重复无遗漏地 列 举出来。 例如：输入 ABC，其全排列的结果有 6 种 ,分别为：ABC,ACB,BAC,BCA,CAB,CBA。 定义 3 (多重集排列 ): 给定的字符串包含重复字母，将其进行全排列，把其 所有可能的全排列 准确 无重复无遗漏地 列 举出来。 例如：输入 AAB，其全排列的结果有 3 种
23、， 分别为：AAB,ABA,BAA。 如果 S 是一个多重集，那么 S 的一个 r 排列 是 S 的 r 个元素的一个有序排放。如果 S 的元素总个数是 n(包括计算重复元素 )，那么 S 的 n 排列也称为 S 的排列。例如，如果 S 3*a , 2*b , 4*c，那么 abbcc , abcac 和 bcccb 都是 S 的 5 排列，而 bccacabca 和 abcabcacc 都是S 的一个排列 60。 定义 4 (字典序排列 ): 所谓字典序排列是指所有可能的排列结果按字典顺序产生。就是预先定义需要排列的 k个元素的次序 1n , 2.knn。给出两个排列 P1和 P2，如果 P1 和 P2的前i 1个元素都相同， P1的第 i个元素为 an ， P2 的第 i个元素为 bn ， ab那么 P1的字典序就先于 P2。例如，在字典序下， 1， 2， 2， 3的排列是 1223， 1232， 1322， 2123， 2132， 2213，2231， 2312， 2321， 3122， 3212， 3221。 定义 5 (非字典序排列 ): 所谓非字典序排列是指生成的所有排列的顺序 可以是随机的，任意的。
