多重集的全排列算法的研究——算法归类分析.doc

1、 本科毕业论文 (科研训练、毕业设计 ) 题 目： 多重集的全排列算法 的研究 算法归类分析 姓 名： 学 院：软件学院 系：软件工程系 专 业：软件工程 年 级： 学 号： 指导教师 ： 职称： 年 月 I 摘 要 排列产生算法的研究在计算机发明之前已被人们所研究，其历史甚至可以追溯到三百年 前 之久。 全排列算法 按处理输入的能力可分为集合 (set)排列算法和多重集 (multiset)排列算法。多重集中一个元素可多次出现，多重集排列算法不会产生重复的排列。 为了更方便区分，在文中分别叫做单重集和多重集排列。 本文旨在对 历史上 一些经典的 全排列算法进行分类 总结 的基础上 ， 着重介

2、绍一种新的全排列算法 TWDRI， 该算法能同时解决 集合排列 问题和多重集 排列 问题；适用于各种不同字符的输入情况，具有通用性。 并且 介绍了从 汇编的角度去分析 新的算法和其他 有代表性的若干算法 的 方法 ， 从而 可以 从理论上去分析它们的优劣，最终得出新算法 TWDRI 具有 效率最好的结论 。 关键词 多重集 ； 排列 ； 算法 ； 汇编 ； 少循 环 II Abstract The permutation has the algorithm research before the computer was invented, and it has been studied by

3、 people, its history even may trace 300 years ago. Permutation algorithms can be divided into two groups: set permutation algorithms and multiset permutation algorithms. Multiset differs from a set in that each member has a multiplicity. For a more convenient discrimination, they are called the pure

4、 permutation and the multiset permutation separately in the article. This article is for the purpose to the history in some classical permutation algorithms carrying on the foundation which the classification summarizes, introduced emphatically one kind of new permutation algorithm TWDRI, this algor

5、ithm can simultaneously solve the pure permutation problem and the multiset permutation questions; and is suitable in each kind of different character input situation. It also has the versatility. And this article analyzes the new algorithm from the assembly angle and other which has the representat

6、ive certain algorithm difference, thus analyzes their fit and unfit quality from the theory, obtains new algorithm TWDRI to have the efficiency best conclusion finally. Key words multiset； permutation； assembly algorithm； loopless III 目 录 第一章 绪论 .1 1.1 课题的背景与意义 . 1 1.1.1 多重集排列的相关定义 . 1 1.1.2 多重集排列的研

7、究历史 . 2 1.1.3 课题的意义 . 3 1.2 本文的主要工作 . 4 1.3 论文的主要结构 . 4 第二章 全排列算法 .6 2.1 递归算法 . 6 2.1.1 算法定义 . 6 2.1.2 算法特征 . 6 2.1.3 经典算法（ heap 算法） . 7 2.1.4 分析总结 . 8 2.2 LOOPLESS 算法 . 8 2.2.1 算法定义 . 8 2.2.2 算法发展 . 9 2.2.3 分析总结 . 13 2.3 GRAY CODE. 13 2.3.1 格雷码的定义 . 13 2.3.2 格雷编码的算法实现 . 13 2.3.3 在全排列的运用 . 15 2.4 汇编

8、分析方法 . 15 2.4.1 MIX . 15 2.4.2 MMIX . 16 第三章 TWDRI算法 . 18 3.1 主要流程 . 18 3.2 算法时间复杂度 . 18 3.3 TWDRI 算法的通用性和创新性 . 20 第四章 模拟比较 . 22 4.1 模拟 测试 . 22 4.2 多重集算法的时间和内存开销比较 . 23 4.3 多重集算法在非重复输入的情况下的时间和内存开销比较 . 24 4.4 TWDRI 算法和其它单重集排列算法的时间和内存比较 . 25 4.5 TWDRI 算法与其它多重集排列算法的比较趋势分析 . 26 第五章 总结与展望 . 28 致谢语 . 29 I

9、V 参考文献 . 30 V Contents Chapter 1 Introduction. 1 1.1 Background and the Significance . 1 1.1.1 The Related Definition of Multiset . 1 1.1.2 The Study History of Multiset. 2 1.1.3 Significance. 3 1.2 Main work . 4 1.3 Main Structure . 4 Chapter 2 The permutation algorithm. 6 2.1 Recurisive Algorithm.

10、 6 2.1.1 Definition. 6 2.1.2 Characteristic. 6 2.1.3 Classical algorithm（ Algorithm heap） . 7 2.1.4 Analysis and Summary. 8 2.2 Algorithm loopless. 8 2.2.1 Definition. 8 2.2.2 Development. 9 2.2.3 Analysis and Summary. 13 2.3 Gray Code. 13 2.3.1 Definition. 13 2.3.2 Algorithm of gray code. 13 2.3.3

11、In the permutation. 15 2.4 Assembly analysis . 15 2.4.1 MIX . 15 2.4.2 MMIX . 16 Chapter 3 Alogrithm TWDRI . 18 3.1 Main Flowchart . 18 3.2 Time Complexity . 18 3.3 Universality and Innovation of TWDRI . 20 Chapter 4 Simulation and Comparison . 22 4.1 Simulation and the results . 22 4.2 Comparison o

12、f Average Time and Memory of Mutliset Permutation . 23 4.3 Comparison of Average Time and Memory of Mutliset Permutation with Distinct Elements . 24 4.4 Comparison of Average Time and Memory of Pure Permutation . 25 VI 4.5 Speed Rations of TWDRI Algorithm to Others . 26 Chapter 5 Conclusions and the

13、 future . 28 Acknowledgements . 29 References . 30厦门大学本科生毕业论文 1 第一章 绪论 一直以来，科学家都 在带领我们认识 我们生活 的 世界，探寻她美丽背后的奥秘。而我们在深入认识事物时总是努力分析其基本构成要素，然后再研究这些要素是如何联系起来构成多种多样不同的整体。尤其是计算机科学家和数学家，在研究中需要列出所有的可能情况以获取一种渴望的特征时，列出排列组合是不可或缺的一步。 DNA 分析、加密解密、电路设计、运筹研究、统计计算、化学 ，这些领域中你都可以看到排列与组合的应用。 1.1 课题的背景与意义 全排列问题 有着悠久的历史。

14、排列 的产生可以追溯到 十六世纪五十年代 ，早在 1960 年就有这一领域算法的总结性文章出现 1112。 一代算法 宗师 Donald E. Knuth在其经典著作计算机程序设计艺术 3一书中写道：“事实上，排列 (permutations)问题在计算机领域非常重要。 Vaughan Pratt 提议直接把它们叫做 perms。如果 Pratt 的建议得以实施 的话 ，那么计算机教科书的厚度将变得薄一些 (相应书的价格也会便宜一点 )”。虽然 Knuth 语带幽默，但由此可见排列在计算机领域出现的频率之高。正是因为排列问题如此重要，所以 在过去的几十年里，一直以来有众多的研究人员致力于该问题

15、的解决 。 下面先介绍一下此课题相关的定义，然后是此论文的研 究历史。 1.1.1 多重集排列的相关定义 定义 1（多重集的长度 N） ： 我们把 N 个字符长度的字符串 S 看成一个多重集，字符串S 包含 k 个不同的字符，每个字符的个数分别为 n0, n1, , nk-1。显然， N = n0 + n1 + nk-1。当 N=k 时，我们把此时的多重集称为 单重集 ，因为此时 n0 = n1 = = nk-1 = 1，每个不同字符的个数有且仅有 一 个。即我们一般意义上的无重复输入。 对于 单重集 1， 2， 3，集合 排列算法给出全部 6 个排列： （ 1） 213 （ 2） 231 （

16、 3） 321 （ 4） 312 （ 5） 132 （ 6） 123 以多重集 1， 2， 2为例，集合排列算法给出该多重集的排列为： （ 1） 212 （ 2） 221 （ 3） 221 （ 4） 212 （ 5） 122 （ 6） 122 厦门大学本科生毕业论文 2 其中 (1)和 (4)是一样的， (2)和 (3)、 (5)和 (6)也是相同的。而我们一般并不希望得到的排列结果中有重复的情况，因此多重集排列算法更具一般性。但也正是因为多重集排列算法需要排除重复的输出，所以多重集排列算法很难达到像集合排列算法一样的性能。 定义 2（重复个数 n0, n1, , nk-1） ： 对于长度为

17、N，有 k 个不同字 符，每个字符个数分别为 n0, n1, , nk-1 的多重集，我们把 n0, n1, , nk-1 称为每个字符的重复个数。 定理 1（多重集的排列数） ： 令 S 是长度为 N 的多重集，它有 k 个不同的元素，每个元素的重复数分别为 n0, n1, , nk-1，那么，多重集 S 的排列数 =0 1 1! !. !kNn n n，其中 N = n0 + n1 + nk-1。 多重集排列是个数学模型，对于每一个输入字符串，多重集排列应该 无重复无遗漏 地列举出所有的可能排列组合。通常，我们随机输入一个长 度为 N 的字符串，希望多重集排列算法能准确快速的产生所有可能的