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

本科毕业论文本科毕业论文 (科研训练、毕业设计) 题题 目：多重集的全排列算法的研究目：多重集的全排列算法的研究 算法归类分析算法归类分析 姓 名： 学 院：软件学院 系：软件工程系 专 业：软件工程 年 级： 学 号： 指导教师： 职称： 年 月 I 摘摘 要要 排列产生算法的研究在计算机发明之前已被人们所研究，其历史甚至可以追溯到三百 年前之久。 全排列算法按处理输入的能力可分为集合(set)排列算法和多重集(multiset)排列算法。 多重集中一个元素可多次出现，多重集排列算法不会产生重复的排列。为了更方便区分，在 文中分别叫做单重集和多重集排列。 本文旨在对历史上一些经典的全排列算法进行分类总结的基础上，着重介绍一种新的 全排列算法 TWDRI，该算法能同时解决集合排列问题和多重集排列问题；适用于各种不同 字符的输入情况，具有通用性。并且介绍了从汇编的角度去分析新的算法和其他有代表性的 若干算法的方法，从而可以从理论上去分析它们的优劣，最终得出新算法 TWDRI 具有效率 最好的结论。 关键词关键词 多重集； 排列； 算法； 汇编； 少循环 II Abstract The permutation has the algorithm research before the computer was invented, and it has been studied by 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 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 algorithm 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 representative 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 多重集排列的研究历史2 1.1.3 课题的意义3 1.2 本文的主要工作.4 1.3 论文的主要结构.4 第二章第二章 全排列算法全排列算法5 2.1 递归算法.5 2.1.1 算法定义5 2.1.2 算法特征.5 2.1.3 经典算法（heap 算法）6 2.1.4 分析总结.7 2.2 LOOPLESS算法 .7 2.2.1 算法定义7 2.2.2 算法发展8 2.2.3 分析总结12 2.3 GRAY CODE12 2.3.1 格雷码的定义.12 2.3.2 格雷编码的算法实现.12 2.3.3 在全排列的运用14 2.4 汇编分析方法.14 2.4.1 MIX.14 2.4.2 MMIX .15 第三章第三章 TWDRI 算法算法.16 3.1 主要流程.16 3.2 算法时间复杂度.17 3.3 TWDRI 算法的通用性和创新性19 第四章第四章 模拟比较模拟比较21 4.1 模拟测试21 4.2 多重集算法的时间和内存开销比较.22 4.3 多重集算法在非重复输入的情况下的时间和内存开销比较.23 4.4 TWDRI 算法和其它单重集排列算法的时间和内存比较.24 4.5 TWDRI 算法与其它多重集排列算法的比较趋势分析.25 第五章第五章 总结与展望总结与展望27 致谢语致谢语28 参考文献参考文献29 IV Contents Chapter 1 Introduction1 1.1 Background and the Significance .1 1.1.1 The Related Definition of Multiset 1 1.1.2 The Study History of Multiset2 1.1.3 Significance3 1.2 Main work.4 1.3 Main Structure 4 Chapter 2 The permutation algorithm5 2.1 Recurisive Algorithm5 2.1.1 Definition.5 2.1.2 Characteristic5 2.1.3 Classical algorithm（Algorithm heap）.6 2.1.4 Analysis and Summary7 2.2 Algorithm loopless7 2.2.1 Definition.7 2.2.2 Development.8 2.2.3 Analysis and Summary.12 2.3 Gray Code.12 2.3.1 Definition12 2.3.2 Algorithm of gray code.12 2.3.3 In the permutation.14 2.4 Assembly analysis.14 2.4.1 MIX14 2.4.2 MMIX.15 Chapter 3 Alogrithm TWDRI.16 3.1 Main Flowchart.16 V 3.2 Time Complexity17 3.3 Universality and Innovation of TWDRI.19 Chapter 4 Simulation and Comparison21 4.1 Simulation and the results 21 4.2 Comparison of Average Time and Memory of Mutliset Permutation.22 4.3 Comparison of Average Time and Memory of Mutliset Permutation with Distinct Elements 23 4.4 Comparison of Average Time and Memory of Pure Permutation 24 4.5 Speed Rations of TWDRI Algorithm to Others 25 Chapter 5 Conclusions and the future27 Acknowledgements.28 References .29 厦门大学本科生毕业论文 1 第一章第一章 绪论绪论 一直以来，科学家都在带领我们认识我们生活的世界，探寻她美丽背后的奥秘。而我 们在深入认识事物时总是努力分析其基本构成要素，然后再研究这些要素是如何联系起来构 成多种多样不同的整体。尤其是计算机科学家和数学家，在研究中需要列出所有的可能情况 以获取一种渴望的特征时，列出排列组合是不可或缺的一步。DNA 分析、加密解密、电路 设计、运筹研究、统计计算、化学，这些领域中你都可以看到排列与组合的应用。 1.1 课题的背景与意义课题的背景与意义 全排列问题有着悠久的历史。排列的产生可以追溯到十六世纪五十年代，早在 1960 年 就有这一领域算法的总结性文章出现1112。一代算法宗师 Donald E. Knuth 在其经典著作 计算机程序设计艺术3一书中写道：“事实上，排列(permutations)问题在计算机领域非 常重要。Vaughan Pratt 提议直接把它们叫做 perms。如果 Pratt 的建议得以实施的话，那么计 算机教科书的厚度将变得薄一些(相应书的价格也会便宜一点)” 。虽然 Knuth 语带幽默，但 由此可见排列在计算机领域出现的频率之高。正是因为排列问题如此重要，所以在过去的几 十年里，一直以来有众多的研究人员致力于该问题的解决。下面先介绍一下此课题相关的定 义，然后是此论文的研究历史。 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 （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）：对于长度为 N，有 k 个不同字符，每个字符个数分 别为 n0, n1, , nk-1的多重集，我们把 n0, n1, , nk-1 称为每个字符的重复个数。 定理定理 1（多重集的排列数）：令 S 是长度为 N 的多重集，它有 k 个不同的元素，每个 元素的重复数分别为 n0, n1, , nk-1，那么，多重集 S 的排列数=，其中 N = n0 + 011 ! !.! k N n nn n1 + nk-1。 多重集排列是个数学模型，对于每一个输入字符串，多重集排列应该无重复无遗漏地 列举出所有的可能排列组合。通常，我们随机输入一个长度为 N 的字符串，希望多重集排 列算法能准确快速的产生所有可能的排列。 例如，当我们输入的字符串为“0112”时，我们可以得到： N = 4, k =3, n0 =1, n1 =2, n2 = 1； 其所有产生的排列数为=12，分别为： 4! 1!2!1! 0211，0112，0121，1210，1201，1021，1120，1102，1012，2011，2110，2101。 1.1.2 多重集排列的研究历史多重集排列的研究历史 大部分科学家，特别是计算机和数学领域的专家，当他们需要列举所有可能性并核对 所希望结果的时候，经常会碰到这样或那样的问题，事实上，这些问题都属于全排列问题。 单重集排列和多重集排列在很多领域都有广泛的应用，例如 DNA 排序，密码学，运筹学， 电路设计，统计学和化学领域等等。 科学家们对于单重集排列和多重集排列的研究，已经有 300 多年历史了。对于单重集 排列的产生算法，百年来可以说不胜枚举。 已知最早的单重集算法 1605 年在英国教堂产生的6，当时，教堂中的牧师用它来计算 几口大钟不同的撞击顺序，以此产生各种不同的音乐效果。其后，具有代表性的算法包括 M. B. Wells12的递归算法和 S. M. Johnson22，H. F. Trotte21具有突破意义的邻位交换法。G. Ehrlic 提出了一种减少内层循环的 loopless 算法，不少研究者紧接着发展了这一算法。另外 厦门大学本科生毕业论文 3 两种算法是字典序法和随机排列法。一代算法大师 Robert Sedgewick 曾于 1977 年对各种单 重集排列的产生算法做了一个全面而深刻的研究3，其中，Sedgewick 指出，Heap1是当时 最快的递归交换算法，同时，Ives2是最快的非递归交换算法。在 2002 年，Sedgewick 又提 出了一个 Heap 递归算法的改进版本6，该算法通过直接排列后三位字符来加快总体排列产 生的速度。 与单重集排列相比，多重集排列算法的发展起步较晚。多重集的排列顺序通常有两种， 字典顺序和格雷码顺序。所谓的格雷码顺序，即每相邻两个排列之间只有一个数位发生变化。 F. Ruskey 认为，按格雷码顺序产生多重集排列的算法是在处理多重集排列问题中最快的算 法8。James F. Korsh 同 Paul S. Lipschutz 在结合 Johnsons 22 和 Lehmers algorithms 算法 的基础上，首次给出了产生多重集排列的少循环算法4。在这个新算法中，多重集的排列是 以链表形式产生的，链表中的操作都是由指针来完成，其中包括 O(1)时间的交换操作。两年 后，Takaoka 使用数组改进了这个 O(1)时间的算法5。Vajnovszki54进一步提出了一种基于 数组的少循环算法。2004 年，James F. Korsh 和 Paul S. LaFollette 提出一种新的少循环算法 9，与以往基于数组的算法不同，这个新算法仅仅需要长度大小的线性存储。Takaoka 和 Violich 于 2006 年又提出一种仅仅使用数组就能在线性空间产生多重集排列的 MULTPERM 算法10，其声称，MULTPERM 算法比 Vajnovszkis 算法更为简单和有效，但是，遗憾的是， 他仅仅使用了两个非常简单的多重集例子（3,3,3,3,3 和 2,3,5,2,3） ，这种比较方法是相 当没有说服力的。另外，尽管不少科学家对多重集排列问题都给出了精妙的算法，但这些算 法都始终没有突破通过保存和判断信息来防止重复输出的思维藩篱。 1.1.3 课题的意义课题的意义 排列问题的一个特点就是输出规模受输入规模的影响极大。我们假设计算机进行一次 运算就能给出一个排列(实际的算法不可能做到这点)。对于一台运算速度为百万次每秒的计 算机， 给出 11 个元素的集合的所有 11！= 399168 个排列只需几秒钟的时间，而给出 17 个 元素的集合的所有 17!= 355687428096000 个排列则需要好几年。 厦门大学本科生毕业论文 4 表 1-1 不同性能计算机在各种输入规模下进行排列所需时间 N排列的个数排列的个数百万百万/秒计算机秒计算机十亿十亿/秒计算机秒计算机万亿万亿/秒计算机秒计算机 103628800 1139916800几秒 12479001600几分钟 136227020800几小时几秒 1487178291200天分钟 151307674368000几周几分钟 1620922789888000几个月几小时几秒 17355687428096000几年几天几分钟 186402373705728000几个月几小时 19121645100408832000几年几天 202432902008176640000月 由上表可以得出，就算是当前最快的计算机，其运算速度达到万亿次每秒，要计算出 大于 20 个元素的集合的所有排列在时间上也显得不太可能。在科学研究中确实可能遇到较 大规模的排列需求，除了配置高性能的计算机之外，找到一个高性能的排列算法就显得非常 必要。 1.2 本文的主要工作本文的主要工作 本文的主要工作是归类历史上比较出名的全排列算法，然后在此归类的基础上提出具 有独创性的 TWDRI 算法，并将新算法和归类的算法用具体的 C 代码进行模拟比较，得出分 析结果。并且尝试着从汇编角度进行分析。所以在本文中着重介绍了在算法领域中经典的汇 编分析方法 MIX 和 MMIX。 1.3 论文的主要结构论文的主要结构 本文首先在第二章就归纳了历史上主要解决排列问题的方法，如递归、无循环等，并 重点对其中的重要方法的发展历程进行总结概括。并且附带一小节介绍了用汇编分析方法分 析算法的优劣。然后在第三章里详细介绍了一种新的算法 TWDRI （Traversal with Dynamic Rest Indices） ，它不仅能处理一般的单重集排列问题，而且能处理更为复杂的多重集排列问 题。其通用性和快速性对于全排列在实际生活中的应用具有深刻的意义。最后得出 TWDRI 微不足道的等待微不足道的等待 时间上几乎不可能时间上几乎不可能 厦门大学本科生毕业论文 5 是当今世界上处理多重集排列问题的最快算法的结论。 厦门大学本科生毕业论文 6 第二章第二章 全排列算法全排列算法 在著名的算法大师 Robert Sedgewick 在 1977 年发表的研究文章中3，他比较了众多关 于单重集排列算法，得到了如下结论， Heap1 是最快的递归交换算法，同时， Ives2是最 快的非递归交换算法。这两种算法都是基于交换实现的。而对于多重集排列问题，F. Ruskey 的按格雷码顺序产生排列的算法是处理此类问题中比较快的算法8。而后，James F. Korsh 同 Paul S. Lipschutz 在结合 Johnsons 22 和 Lehmers algorithms 算法的基础上，首次给出了 产生多重集排列的少循环算法4。在这个新算法中，多重集的排列是以链表形式产生的，链 表中的操作都是由指针来完成，其中包括 O(1)时间的交换操作。下面，本文对各种产生排列 的方法进行总结归纳。 2.1 递归算法递归算法 递归算法是研究全排列算法的先驱。 Heap 是递归算法中的杰出典范。其根本思想在于用简单的判断算法得出进行换位的两 个位置，既而递归处理以得到快速排列结果。 2.1.12.1.1 算法定义算法定义 递归概念在计算机程序的调用方面的定义, 便是一个函数直接或间接地调用它本身。一 个函数直接的调用它本身就称为直接递归, 如果一个函数调用了另一个函数, 而这另一个函 数反过来又调用前一个函数, 这种情况称为间接递归。 2.1.22.1.2 算法特征算法特征 能采用递归描述的算法通常有这样的特征：为求解规模为 N 的问题，设法将它分解成 规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问 题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出 规模较大问题的解。特别地，当规模 N=1 时，能直接得解。 厦门大学本科生毕业论文 7 递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为 N）的求解推到比原问题简单一些的问题（规模小于 N）的求解。在递推阶段，必须要有终 止递归的情况。 在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解， 2.1.32.1.3 经典算法（经典算法（heapheap 算法）算法） Heap 算法是几十年来递归算法中公认最快的算法。 定义定义 3（P数组）：Pi是 N 位长度字符串中每一位的字符，i=1,2N。 定义定义 4（c数组）：ci是调用递归函数 Permutation(i)时内部控制循环的计数器， i=1,2N。 伪代码如下： proceduce Permutation( i:N ) begin i:=N; loop: ci:=1 while i2: i:=i-1 repeat; process; loop if ci 1 9do i N 10 x 0 11 while ci = i 12do if di = false 13 then x x + 1 14 if di = true 15 then di false 16 if di = true 17 then k ci + x 18 else k j ci + x 19do swap pk pk+1 20ci ci + 1 21OuputPerm 上一步我们从B, C, D, E的 1 个排列得到了A, B, C, D, E的 5 个排列。为了产生过程 继续进行，首先需要得到B, C, D, E的另一个排列，同样我们把 B 看成是新元素插入到 厦门大学本科生毕业论文 11 CDE 的排列中得到 CBDE。现在就可以把 A 插到 CBDE 的空隙中得到另外 5 个排列了。图 2-4 表现的就是上面的过程。 A B C D E B C D E A C B D A E C B A D E C A B D E A C B D E C B D E A 图 2-4 BCDE 换为 CBDE 后 A 向反方向移动 从图 2-5 可以看出 N 个元素的排列网络中被框起来的部分构成了 N-1 个元素的排列网 络。也可以看成是在 N-1 个元素的排列网络中插入第 N 个元素从左到右的移动或是从右到 左的移动便得到 N 个元素的交换网络。 A B B A A B C B A C B C A C B A C A B A C B A B C D B A C D B C A D B C D A C B D A C B A D C A B D A C B D A C D B C A D B C D A B C D B A D C B A D C A B D A C B A D C B A D B C D A B C D B A C D B C A B D C A B D A C B A D C A B D C N = 3 N = 2 N = 4 图 2-5 Johnson-Trotter 算法在 N = 2，3，4 时产生排列的交换过程 LooplessLoopless 算法算法 厦门大学本科生毕业论文 12 Ehrlich 改进了 JT 的算法，使其成为 loopless 算法，算法伪代码如下： 1. (initialization) Start with: P0, Pn+1n+1 For each 1kn, set IPk,Pkk All elements of D are equal to -1 cn Tn-2 Tc0 2. OUTPUT 3. If c=0 then STOP 4. (Generating the new permutation) Transpose P(IPc) with P(IPc+Dc) 5. (Update IP) Transpose IPc with IP(P(IPc) 6. Check if i 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; 基于格雷码顺序的排列产生结果: A B C A C B C A B C B A B C A B A C 图 2-6 当 N=3 时，基于格雷码的多重集排列算法的排列产生图 厦门大学本科生毕业论文 15 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-7 当 N=4 时，基于格雷码的多重集排列算法排列产生图 2.3.32.3.3 在全排列的运用在全排列的运用 在业界，经常按照格雷码的次序列出多重集的排列。遵循这种方法所得到的排列结果 中任何连续的排列只有两处不同于它的前一排列和它的后一排列。 基于格雷码的算法自从它诞生以来，得到了长足的进步，从一种最初的灵感逐渐成为 一种成熟的机制，尤其是进入 21 世纪之后，很多学者又开始对以前的经典格雷码算法进行 改进，并且又提出了很多新式的格雷码算法，这些算法的普遍特点都是把格雷码机制运用的 越来越灵活，越来越合理。 2.4 汇编分析方法汇编分析方法 F.M. Ives 在其文章 Permutation Enumeration: Four New Permutation Algorithms 中对文指 出算法比较采用计算操作次数比计算时间相比更加的合理。在其文中采用分别计算每个算法 的赋值、算术运算、比较、下标索引四个分类的操作次数，这样的方法同样不能很好地比较 各个算法，因为对操作的分类太为宽泛，同类的操作运行的时间可能会相差很大。全排列领 域的大师在其 1977 经典文章中也采用了汇编的分析方法对 Heap 与 Ives 算法进行分析比较。 其使用一种设想的汇编语言来编写，所有操作与内存访问无关的定义其执行时间为一个单位， 相需要操作内存的则为两个时间单位。该方案同样是存在计算不精确的问题，但该方法中还 是有很多可以参考借鉴的。 经过搜集大量的资料，最终确定使用 Knuth D.E. 的名著计算机程序设计语言艺术 中所使用的算法分析方法，下面简单介绍一下这种汇编语言。 2.4.1 MIX MIX 是著名算法大师 Donald E. Knuth 发明，并出现在他的著作The Art of Computer 厦门大学本科生毕业论文 16 Programming中。据世界首富比尔盖茨的评价， The Art of Computer Programming这 部书被誉为 20 世纪最重要的 20 部著作之一，并且与爱因斯坦的相对论并列，与牛顿的 自然科学的数学原理媲美，乃计算机科学领域的权威著作，全书共分七卷，作者数学方 面的功底造就了本书严谨的风格，虽然本书不是用当今流行的程序设计语言描述的，但是丝 毫不损它“程序设计史诗”的地位，道理很简单，它内涵的设计思想是永远不会过时的。 在本书中第一卷用的机器语言就是作者发明的 MIX 汇编语言，MIX 是一台想象中的计 算机，它除了更加精巧外，几乎非常类似现有的每一台计算机。MIX 语言是经过作者精心 设计的，与大多数现有的机器语言及其类似，所以 MIX 的特征是易于理解的。MIX 有一个 独特的性质，即它同时既是二进制的又是十进制的。程序员不必实际地知道他是正在以二进 制还是正在以十进制来对一台机器进行程序设计。这样就使得以 MIX 语言写成的算法，稍 经变化就可以为每一种类型的机器所用。而且也使得每一种类型的机器上可以容易地来模拟 MIX。下面先介绍一下 MIX 计算机的组成部分。 一台 MIX 包括： 1.9 个寄存器。 2.一个溢出开关（只有一位，或者为“开” ，或者为“关” ） 。 3.一个比较指示器（有三个值：L（小于） ，E（等于） ，G（大于） ） 。 4.存储器（4000 个存储字） 。 5.还有输入输出装置（如卡片，带等） 。 但是这次我们用的汇编语言不是 MIX，而是新版的The Art of Computer Programming里面出现的一个新的代替 MIX 的汇编语言 MMIX。 2.4.2 MMIX 这一小节介绍的是我们这次选用的汇编语言 MMIX。而 MMIX 是 Donald E. Knuth 在他 的著作The Art of Computer Programming中首次介绍给大家的，它是在其前身 MIX 的基 础上的改进版本。因 MIX 中一个字节只有 6 位，已经不满足现在编程的需要了，所以作者 用 MMIX 代替了 MIX。MMIX 比现在所有的处理器设计都要干净利落，而且溶合了各种处 理器的优点。 MMIX 是一个多种未饱和的、100%自然的计算机。和大多数机器一样，它有一个标识 的数字2009，这个数来自于取 14 种非常类似于 MMIX 而且在这些机器上可以容易地模拟 厦门大学本科生毕业论文 17 MMIX 的实际计算机，然后以相同的权来对它们的号码求平均值： （Cray I+IBM 801+RISC II+Clipper C300+AMD 29K+Motorola 88K+IBM 601+Intel i960+Alpha 21164+POWER 2+MIPS R4000+Hitachi Super H4+Stong ARM110+Sparc64） /14=2009 MMIX 的特点：它通常一次处理 64 位（二进制） 。一个 MMIX 计算机有 264 个存储单 元和 28 个通用存储器，和 32 个专用寄存器。遵循了 RISC 思想, 只加入了必须或者是很有 用的指令。子程序调用采用“寄存器栈“, 整个操作在一个周期完成, 相当于有很多个可变大 小，可变重叠区大小的 RISC II 寄存器窗口, 栈的内容大部分时间不需进入内存，这比普通 的“存储器栈“快的多, 而且比 RISC II 式的寄存器使用效率高。进程切换时只需要把用过的 寄存器入栈，加速了切换。具有强大的整数运算能力, 具有其它芯片没有的强大的 MOR 和 MXOR 指令。 具有大量通用寄存器（至少 256 个） ， 大大减少 MMIX 程序的长度和对内存 的访问次数。 对 IEEE 浮点数的 FINT 和 FREM 指令非常高效。 指令格式统一，所有指令 很容易手工汇编。 厦门大学本科生毕业论文 18 第三章第三章 TWDRI 算法算法 在这章中详细介绍了我们的新算法 TWDRI，主要从其主要流程、算法时间复杂度及其 的创新之处介绍。 3.1 主要流程主要流程 TWDRI 算法是一种新的快速的全排列产生算法。该算法能同时解决一般的无重复输入 的单重集排列问题和重复输入的多重集（Multiset）排列问题。程序根据输入字符串，自动 选择处理处理单重集排列问题的 PurePermutation()函数，或者处理多重集排列问题的 MultisetPermutation()函数，从而，既满足了输入字符串的随机性，又达到了快速处理两种不 同集合的排列问题。 以下是算法其主要流程图： Start Input a string Initialization() N=k PurePermutation(N-1,0)MultisetPermutation(N-1,0) End YN 图 3-1 TWDRI 算法的主要流程图 3.2 算法时间复杂度算法时间复杂度 厦门大学本科生毕业论文 19 算法的计算时间 T(n)满足： 12 3 (1)*(3) ( ) (3) nT nCnCn T n Cn 输入规模为 n3 的问题可由 n 个输入规模为 n-1 的子问题构成。是对子问题 12 *CnC 结果进行分解和合并的花费，其中、为常数。当 n=3 求解问题的花费为，为常数。 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-2. 的递归树 12 ( )(1)T nnT nC nC 从树的根结点开始,根有 n 个分支，第二层的每个节点有 n-1 个分支，一直到倒数第二 层的每个节点有 2 个分支，共 n+1 层。树的第一层有 1 个节点，第二层有 n 个节点，以下各 层依次节点数为 n(n-1)、n(n-1)(n-2),最后一层为 n!个。 接下来分析在每层的花销。TWDRI 算法的最大特点在于随着递归层数的增加子问题的取 值空间不断缩小，因此，在每个节点上对子问题的分割和合并的花费也从第一层的 到最后一层的 C C1 1+C+C2 2不断下降。 12 *CnC 本文的算法无需到达树结构的最后一层，而在倒数第三层时便能输出排列。因为在递 归树中一层节点的数目与其以上所有祖先节点的数目之和相近，所以最低两层的排除能带来 性能的巨大提高。 总的时间花费有： 厦门大学本科生毕业论文 20 121212 ( )()(1)*(2)* (1).T nC nCC nCnC nCn n + 12 5 (4) n i CCi 3 4 n i Ci 1 4 (1)(1)(2).) n i C nn nn nni + 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 123 5171 ()() ! 266 C eC eCn 对于输入元素个数为 n 的全排列问题，其输出的规模为 n!。因此时间复杂度中的 n！ 是由问题本身固有的内在特点所决定的。本文算法的时间复杂度最终可以表示为 C*n!(C 为 常数)，即从渐进意义上已达到排列问题时间复杂度的理论下界。 在大多数时间复杂度的分析中，常数 C 都是对程序中语句行数的计算。为了进行较为 精确的分析我们采用了和 Ives 相同的方法，计算程序中的赋值、数值运算、比较和下标引 用的使用次数。 3.3 TWDRI 算法的通用性算法的通用性和创新性和创新性 定义定义 9 （Mappings数组）对于长度为 N、有 k 个不同字符，每个字符个数分别为 n0, n1, , nk-1的字符多重集，我们引进数组 Mappings来映射 k 个不同字符。k 此时为 Mappings 数组的长度。 Mappingsi = ni所对应的不同字符，当 i = 0, 1, 2, , k-1 例如，当输入字符串为“0112”时，我们可以得到： 厦门大学本科生毕业论文 21 N = 4, k =3, n0 =1, n1 =2, n2 = 1; Mappings0 = 0, Mappings1 = 1, Mappings2 = 2； 同理，当输入字符串为“abbc”时，我们可以得到： N = 4, k =3, n0 =1, n1 =2, n2 = 1; Mappings0 = a, Mappings1 = b, Mappings2 = c； 显然，对于以上两个例子，虽然输入不同，但是，它们映射到了相同的数字多重集 0,1,1,2。 与已有算法不同，TWDRI 采用了 Mappings数组,将各个不同输入字符一对一映射到连 续的自然数数组，排列过程中仅仅对此自然数组进行操作。由于最后排列的产生是根据自然 数与字符对应关系得到的，这样，既解决了传统的多重集问题，又满足了一般字符的随机输 入，具有广泛的通用性。 更为难得可贵的是，TWDRI 算法没有进行换位，也没有按照格雷码顺序，在速度上就 超越了原有已知的解决相同问题的最快算法，从而，打破了传统解决单重集排列问题中最快 算法都是基于换位的一般看法，也打破了多重集问题中最快的排列产生方法是基于格雷码顺 序的论断。具有历史创新性。 厦门大学本科生毕业论文 22 第四章第四章 模拟比较模拟比较 4.14.1 模拟模拟测试测试 借鉴以往大型模拟比较的经验56，我们把 TWDRI 算法同 11 种已知最快或最新的算法 进行模拟比较。为保证比较的的科学性、准确性和公平性，所有的算法都用 C 语言实现，并 且运行在相同配置的计算机上（Pentium 4 CPU 2.93 GHz、1 GB 内存） 。 从通用性出发，我们模拟测试选择的字符串从字符 0-9 和 a-j 中选出。例如，当模拟单 重集算法时，如果 N=5，模拟测试的字符串为 “01234；如果 N=17，模拟测试的字符串则 为“0123456789abcdefg”。 以下是缩写说明: Heap63: 递归交换算法 1 Heap63: 非递归交换算法 1 Ives 76:非递归交换算法 2 JT: 算法 3b-少循环的 Johnson-Trotter 算法 3 JTLLC03: Jeeve Technologies LLC 算法 7 KL97: Korsh 和 Lipschutz 常数时间算法 4 KL04: Korsh 和 LaFollette 基于数组的少循环算法 9 KnuthLex08: 字典序算法57 OurKnuthLex:字典序算法 OurKnuthNoLex:非字典序算法 PhilLex67 字典序算法31 Ruskey 03: Ruskey 算法 53 Sedgewick02: Sedgewick 算法 6 Takaoka99: Takaoka 的 O(1)算法 5 TV06: Takaoka 和 Violich 的算法 10 厦门大学本科生毕业论文 23 4.24.2 多重集算法的时间和内存开销比较多重集算法的时间和内存开销比较 表 4-1 和图 4-1 说明 TWDRI 算法在处理多重集问题中，速度至少是其它 7 种算法中任 何一个的 2 倍。并且仍然比 OurKnuthLex 和 OurKnuthNoLex 快。表 4-2 则说明 TWDRI 算法 内存开销相对其它算法较少，但是没有 Ruskey03 少。 表 4-1 多重集排列算法的平均时间比较 (单位：毫秒) N11121314151617 TWDRI7858168,63797,9821,192,54015,243,359 KL042202,03620,389218,8242,532,981 KL971391,31812,695141,9081,568,173 KnuthLex08191721,72718,212208,727 OurKnuthLex9828108,66198,9851,213,931 OurKnuthNoLex9807958,58198,0601,200,86015,838,302 PhilLex671771,67417,160181,431 Ruskey03524794,77951,654595,2497,411,564 Takaoka 994404,20242,175457,8655,234,257 TV061491,36913,729146,3591,684,183 0.E+00 2.E+06 4.E+06 6.E+06 8.E+06 1.E+07 1.E+07 1.E+07 2.E+07 2.E+07 11121314151617N time(ms) TWDRIKL04KL97KnuthLex08 OurKnuthLexOurKnuthNoLexPhilLex67Ruskey03 Takaoka 99TV06 图4-1 多重集全排列算法的平均时间比较 厦门大学本科生毕业论文 24 表 4-2 多重集全排列算法峰值/平均内存比较 (单位：KB) N111213141516 TWDRI776776780780784784788788800800808808 KL04780780788788792792796796804804 KL97813813832832859859897897941941 KnuthLex08780780784784784784792792796796812812 OurKnuthLex7887887927927927928008001211121112121212 OurKnuthNoLex7887887927927927