1、I 多重集的全排列算法研究暨分类 摘 要 本文 介绍一种新式的， 经过 优化了的多重集全排列算法 TWDRI。同时， 本文 也分析了所有的多重集 全 排列算法 并按照算法的实现机制进行了分类。为了公平起见，本文通过 经验总结出一套模拟和比较算法的机制，并很好地应用在了 TWDRI 与其他 同类算法的性能比较里面。 值得 庆幸的是 ， TWDRI 确实能够为多重集 的 全 排列 和纯排列 处理提供理想的速度。论文剩余的部分 将 研究格雷编码在多重集 全 排列领域中的应用。 并 总结了从格雷编码第一次被应用到此领域一直到 现在 的应用 情况和评论，以及一些相关的 问题，其中有 些问题一直到现在还是
2、处于 未解决阶段。在最后，将展望一下多重集 全 排列算法的一些可能的发展前景，将从目前正在进行的甚至到未来可能的发展方向做个综述，希望以后可以 为 这个领域进行进一步的研究打下基础。 关键词 TWDRI 算法 算法比较 全排列 格雷编码 II Abstract The thesis is going to introduce TWDRI, a new optimized permutation algorithm of multiset. At the same time, almost all the algorithms of permutation of multiset are ana
3、lyzed and classified due to their inner principles. To be equitable, we employ methodology summarized from experience to simulate and compare data of TWDRI to other well known/unknown algorithms in this field. We are pleased to see ideal speed in both pureset and multiset permutation processing. In
4、the remainder of this thesis, we pay main attention to Gray code applied in the said field. We focus on its development progress status from when Gray code first introduced into this field to the newest application and comments, and some open problems would be issued which have not been resolved unt
5、il now. In the end, expect possible development prospect and summarize direction developing and future of permutation of multiset, with the hope of constructing basis for possible future further studies in this said field. Key words TWDRI; multiset; pureset; permutation; Gray code; algorithm III 目录
6、第一章 绪论 . 1 1.1 课题背景和存在的问题 . 1 1.1.1 排列历史 . 1 1.1.2 纯排列算法的历史 . 1 1.1.3 多重集的全排列算法的历史 . 2 1.1.4 排列中的格雷码 . 2 1.2 论文的主要内容 . 2 1.3 论文的组织结构 . 3 第二章 已有的排列算法的分析总结和分类 . 4 2.1 基本概念 . 4 2.2 分析总结与分类 . 7 第三章 新式的高性能的排列算法 TWDRI . 16 3.1 算法流 程图 . 16 3.2 算法的时间复杂度分析 . 17 3.3 算法的应用和特点 . 18 第四章 排列算法中的格雷码应用研究 . 20 4.1 初步
7、的发展 . 20 4.2 新世纪的发展 . 21 第五章 测试、模拟与比较 . 24 5.1 基于随机输入的平均时间计算模型 . 24 5.2 计算模型的推导过程 . 24 5.3 模拟之后的比较结果 . 26 5.3.1 多重集排列算法的时间和内存开销比较 . 26 5.3.2 多重集算法在纯排列的情况下的时间和内存开销比较 . 28 5.3.3 TWDRI 算法和其它纯排列算法的时间和内存比较 . 29 IV 5.3.4 TWDRI 算法与其它多重集排列算法的比较趋势分析 . 30 第六章 总结与展望 . 32 致谢 . 36 参考文献 . 37 V Contents Chapter 1
8、Introduction . 1 1.1 Background and Problems . 1 1.1.1 History of Permutation . 1 1.1.2 History of Pureset Permutation Algorithm . 1 1.1.3 History of Multiset Permutation Algorithm . 2 1.1.4 Gray Code in Permutation . 2 1.2 Main research . 2 1.3 Outline of Thesis . 3 Chapter 2 Analyse, summarise and
9、 classify existent permutation algorithms . 4 2.1 Basic concept . 4 2.2 Summary and classification . 7 Chapter 3 A new permutation algorithms with high performanceTWDRI . 16 3.1 Flow chart of algorithm . 16 3.2 Analysis of time complexity . 17 3.3 Features and application. 18 Chapter 4 Studies on Gr
10、ay code applied in permutation algorithms . 20 4.1 Primary development . 20 4.2 Development in new century . 21 Chapter 5 Testing, simulation and comparison . 24 5.1 Computing Model Based on Random Input . 24 5.2 Derivation of Computing Model. 24 5.3 Summary of Comparison after Simulation . 26 5.3.1
11、 Comparison of Average Time and Memory of Mutliset Permutation . 26 5.3.2 Comparison of Average Time and Memory of Mutliset Permutation with Distinct Elements . 28 VI 5.3.3 Comparison of Average Time and Memory of Pure Permutation . 29 5.3.4 Speed Rations of TWDRI Algorithm to Others . 30 Chapter 6
12、Conclusions and Future Work . 32 Acknowledgements . 36 References . 37 1 第一章 绪论 本章首先介绍了 论文中研究的两大 课题 即多重集的全排列算法和格雷 码 的背景 。 然后分别对 多重集 全排列算法的 意义和 在世界范围内 研究现状 进行介绍，给出 了 本文的主要内容和特色的概括 ， 并介绍了本文的架构和组织灵感 。 1.1 课题背景 和存在的问题 首先对多重集全排列领域的历史进行综述，主要从纯排列和多重集排列两个角度对算法的历史和一些主要问题进行阐述，为本文以后的解决问题做一个铺垫。 1.1.1 排列历史 有关纯排列
13、和多重集的排列的研究已经有 600 年的历史了。现在，大多数计算机科学家经常遇到很多关于多重集 的排列问题，目前排列多用在诸如 DNA 排序，加密系统设计，计算机统计以及生物化学领域。世界上已有很多种排列算法，其中大多数是处理纯排列 (即无重复的数字出现的集合 )的，处理多重集排列的比较少。而且其中的很多算法还没有经过可靠并且详尽的数据模拟和比对就给出了一些结论，有时这些结论只在特殊例子下才是成立的，也就是说很多结论是不严谨的，我们也迫切的需要一个比较全面而且严谨公平的算法性能比较方法。 1.1.2 纯排列 算法的历史 至今最早知道的纯排列算法产生于 17 世纪中叶的英国教堂。此后一并产生了很
14、多具有代表性的算法， 这其中包括一些递归的和邻近元素交换的处理方法。邻近元素交换的思想也被认为是该领域的一项重大突破。紧接着 Ehrlich 就发明了一种可以减少内层循环的算法并被很多研究者改进。除此之外还有其他两种比2 较主流类型的算法分别是字典序算法和随机排列算法。在 1977 年， Sedgewick对排列算法做了一个阶段性的详细总结。在所有这些算法中， Heap63 算法被公认是世界上最快的递归交换算法，而 Ives76 是世界上最快的迭代交换算法。Sedgewick 随后在 2002 年通过把 Heap63 排列算法中的最后三位数单独提出来进行直接排 序的方式提高了该算法的速度。 1
15、.1.3 多重集的全排列 算法的历史 多重集排列算法的出现最早可以追溯到 14 世纪印度的一种被称作“ lexicographic permutation generation”的算法，这个算法直到 1967 年才再一次被 Phillips 优化并得到了速度上的提高。为了进一步提高这个经典的字典序排列算法， Knuth 在 2008 年继续对 Phillips 的算法进行了优化并取得了将近十倍的速度提升。本文中将把这个算法命名为“ KnuthLex08”。这也是目前所有已经发布的多重集排列算法中速度最快 的。 1.1.4 排列中的格雷码 在业界 中 ， 有很多算法是遵循格雷码的输出机制输出排列
16、结果的 。遵循这种方法所得到的排列结果中任何连续的排列只有 一处或者 两处不同于它的前一排列和它的后一排列。 其中产生的相异处的数目需要看不同的实际情况而定。 1.2 论文的主要内容 本文在 03 级学长的工作成绩基础上进行了以下几个方面的工作： 1. 优化了我们自己原创的排列算法，使其速度达到世界上的一流水平，以供和同类的排列算法进行比较。 2. 根据算法思想实现了更多的同类的排列算法代码，并应用平均时间测试模型模拟和比较算法的结果，以此证明 我们原创算法的优越性。 3. 对于格雷码在排列算法中的应用进行分析和概括，并总结格雷码应用的优势和问题。 3 1.3 论文的 组织 结构 下面介绍本文
17、的组织和架构灵感， 本文共分为以下几个部分： 第一章， 绪论 。简述了 纯排列和多重集排列的背景 、 发展和现状，格雷码在排列 算法领域中的应用 背景 和意义 。 第二章，对目前世界上的排列算法进行分析总结并分类，我们希望按照主题关键字诸如递归，格雷码， Loopless 等进行分类，以此可以对整个排列算法的发展有一个比较全面的概念。 第三 章， 将会推出我们的新式的高性能的基于树遍历的算法 TWDRI。 第四章， 将讨论格雷码在排列算法历史中的扮演的角色和对后来算法发展的影响。 第五章， 给出 TWDRI 和其他同类排列算法的模拟方法和比较结果，并总结出各个算法在不同的情况下所具有的优点和不
18、足。 第六章，对我们提出的 TWDRI 算法的速度提升的可能方向进行假设，并给出可行性分析，最后给出此次毕设的结论。 4 第二章 已有的 排列算法的分析总结和分类 每个领域的算法都是看似纷乱实际上是可以按照算法的本质 或者实现机制进行分类总结的，排列算法也不例外。对于现在业界众多的排列算法，宏观上看是各有优点，各有千秋的，但是总 的来说可以分为几大类，本章 将首先 对它们定性后，进行一下 详细的 分类 和分析 总结。 2.1 基本概念 首先介绍一些本文中必需的一些基本概念。 1） 多重集全排列的定义 多重集就是允许数字重复出现的数的集合。多重集的全排列是对数字的集合进行排列，并按照一定次序输出
19、排列的数学模型，如果多重集里面没有重复出现的数字（即是数字都是互异的），则该集合的排列被我们称为是纯排列。 2） 格雷编码的定义 格雷码 是一个数列集合，每个 数 使用 二进制数 来表示，假设使用 n位元来表示每个 码 ，任两个 码 之间只有一 个位 元 的 值不同，例如以下为 3 位元的 格雷码 ：000 001 011 010 110 111 101 100 000 001 011 010 110 111 101 100。 由 此可以知道， 格雷码 的 顺序 並不是 唯一 的 。 格雷码 是由 贝尔实验室 的 Frank Gray 在 20 世纪 40 年代提出的，用 来 在使用 PCM（ Pusle Code Modulation）方法 传送信号时避免出错。 格雷码的数的变化是有规律的。首先 观察奇数项的变化时，我们发现无论它是第几个 格雷码 ，永远只改变最右边的位元，如果是 1 就改为 0，如果是 0就改为 1。观察偶数项的变化时，我们发现所改变的位 元，是由右边算 过 来第一个 1的左边位元。
