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

厦门大学本科毕业论文 1 本科毕业论文本科毕业论文 (科研训练、毕业设计) 题题 目：多重集的全排列算法研究目：多重集的全排列算法研究 姓 名： 学 院：软件学院 系： 专 业：软件工程 年 级： 学 号： 指导教师（校内）： 职称： 年 月 厦门大学本科毕业论文 2 多重集全排列算法研究多重集全排列算法研究 摘要摘要 排列产生算法的研究在计算机发明之前已被人们所研究，其历史甚至可以追溯到三 百年之久。本文提出一种新的全排列产生算法 TWDRI。该算法能同时解决一般的无重复输入 的单集问题和重复输入的多重集(multiset)问题。TWDRI 突破了以往只有采用换位思想才能 达到最快速度的传统思想的束缚，以自身独特的数据结构设计为基石，充分利用递归方式的 优势，取得远优于其他同类算法的速度和内存损耗。此外，不同于大多数排列产生算法只能 处理数值的特性，本算法适用于各种不同字符的输入情况，具有通用性。为了能客观评价现 有各种排列算法的性能，本文提出了一种新的性能计算模型，可以精确的测出各类算法的平 均运行时间。在此基础上，我们进行了大量的模拟，测试了从 10 位到 17 位的输入情况，与 已知最快和最近的算法进行比较12345678910，TWDRI 的速度处于领先水平。 关键词关键词 多重集 全排列 算法 厦门大学本科毕业论文 3 A Research into Multiset Permutation Algorithm Abstract TWDRI 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, respectively. 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. 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 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 todays 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 目录目录 第一章第一章引言引言.5 第二章第二章研究背景研究背景6 2.1 问题定义 6 2.2 主要算法 6 2.2.1 字典序算法.6 2.2.2 Heap 算法7 2.2.3 Ives 算法8 2.2.4 Johnson and Trotter 算法10 2.2.5 Constant Time 算法12 2.3 应用 .13 第三章第三章TWDRITWDRI.14 3.1 算法流程图 .14 3.2 算法思想 .14 3.3 例子 .15 3.4 时间复杂度分析 .15 第四章第四章测试模型测试模型18 第五章第五章测试结果测试结果20 5.1 TWDRI 算法和其它单集排列算法的速度和内存比较20 5.2 多重集算法的时间和内存开销比较 .21 5.3 多重集算法在非重复输入的情况下的时间和内存开销比较 .22 5.4 TWDRI 算法与其它多重集排列算法的比较趋势分析 .23 第六章第六章结论结论.25 致谢语致谢语 26 参考文参考文献献27 厦门大学本科毕业论文 5 Contents Chapter 1 Introduction.5 Chapter 2 Background6 2.1 Definition6 2.2 Classic algorithms.6 2.2.1 Lexicographic Algorithm.6 2.2.2 Heap Algorithm7 2.2.3 Ives Algorithm .8 2.2.4 Johnson and Trotter Algorithm10 2.2.5 Constant Time Algorithm 12 2.3 Implementation.13 Chapter 3 TWDRI.14 3.1 Main Flowchart.14 3.2 Main Idea14 3.3 Example15 3.4 Time Complexity Analysis.15 Chapter 4 Testing Model18 Chapter 5 Test Result20 5.1 Pureset Permutation Algorithms Comparisions .20 5.2 Multiset Permutation Algorithms Comparisions21 5.3 Multiset Permutation Algorithms Comparisions with Distinct Inputs.22 5.4 Trends Analysis23 Chapter 6 Conclusion.25 Acknowledgements26 References.27 厦门大学本科毕业论文 6 第一章第一章 引言引言 万花筒般美丽繁华的万千世界之所以异彩纷呈，并不因其本质有何等的错综复杂。洗尽 铅华后，人们发现纷繁的背后往往只是些看似平凡无奇的事物的排列组合，就好像简单几个 小纸片和小镜片的巧妙搭配就能焕发出万花筒炫目的五光十色。在科学界，排列组合问题更 是与科学家们如影相伴。爱迪生经过两千多次的各种材料的排列组合才找到发明电灯的方案； 袁隆平也是经历了无数次的组合排列实验才找到了优质的杂交水稻。排列组合广泛的应用范 围和重大的科学意义促成了研究者们数百年来孜孜不倦的追索和探求123456789101112 131415161718192021222324252627282930313233343536373839404142434445464748 49505152535455。 溯其根源，可以回到那遥远的十六世纪五十年代，教堂中的牧师计算几口大钟不同的撞 击顺序来产生各式的音乐效果。早在 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-Trotter 算法的另一种实现；同样是在 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；比较有影响的 算法还有 Lexicographic algorithms1116181922252930与 Random permutations1323242731。 以上这些算法仅能解决无重复输入的问题。多重集(multiset)输入是一个相对较难的问题， 不少研究者一直在寻求一个高性能的算法45384054。在求解多重集排列问题时传统算法为 防止重复输出而保存大量纪录信息，许多研究人员投入经历简化纪录信息的保存和判断验证 过程，也产生了许多精妙的算法。但这些算法都始终没有突破通过保存和判断信息来防止重 复输出的思维枷锁。 厦门大学本科毕业论文 7 第二章第二章 研究背景研究背景 2.12.1 问题定义问题定义 定义定义 1 1 （单集） 对于一个长度为 N 的字符串来说，如果它有 k 个不同的字符，每个字 符重复出现的次数均为 1，即 N=k, 我们称这样的输入为单集，其排列称为单集全排列。 定义定义 2 2 （多重集） 对于一个长度为 N 的字符串来说，如果它有 k 个不同的字符，每 个字符重复出现的次数分别为：n0, n1, , nk-1（这些数不全为 1） 。我们称这样的输入为多 重集, 它们的全排列问题也因此被称为多重集全排列问题。 定理定理 1 1 （多重集长度特性） 对于一个长度为 N 的多重集，它有 k 个不同的字符，每个 字符重复出现的次数分别为：n0, n1, , nk-1。N = n0 + n1 + nk-1。 2.22.2 主要算法主要算法 单集全排列问题在 1977 年 Sedgewick 的综述性论文3后几乎很难有重大的突破，最为 人们所熟知的字典序法，最优秀最经典的是迭代算法 Ives2。在递归算法领域中则以 Heap1一支独秀。另外一篇具有奠基意义的是 Johnson and Trotter2021算法，曾引发了一 场研究 Loopless 算法的热潮9103346485154。相比单集，多重集的研究则有更大的发展 空间。Constant Time4算法是这方面的代表。 .1 字典序字典序算法算法 字典序是排列算法中最经典的算法，在各种排列场合下被广泛引用。字典序排列算法 的优点是简单易懂，规律性强。但要实现从一个排列得到它的下一个排列通常需要较多的 操作。 以集合A、B、C为例，按字典序生成的全排列是：ABC,ACB,BAC,CAB,CBA。字典 序法就是预先定义需要排列的 k 个元素的次序 n1,n2.nink。给出两个排列 P1和 P2，如果 P1和 P2的前 i1 个元素都相同，P1的第 i 个元素为 na，P2的第 i 个元素为 nb，a 2: i:=i-1 repeat; process; loop if ci 1; Do IF ci 1 i = N; x = 0; While ci = = i IF di = = false THEN x = x + 1; ENDIF 厦门大学本科毕业论文 12 IF di = = true THEN di = false; ELSE di = true; ENDIF END While IF di = = true THEN k = ci + x; ELSE k = i ci + x; ENDIF tem = Pk; Pk = Pk+1; Pk+1 = tem; ci = ci + 1; OutputPerm; END While .5 ConstantConstant TimeTime 算法算法 Constant Time4能产生多重集的全排列。算法思想是从当前一个排列到下一个排列产 生所需要的时间是常数。 我们以多重集11223444为例，来说明其是如何产生多重集的全排列。 图 2-6 1，1，2，2，3，4，4，4在 Constant Time 算法下的全排列 首先，11223444 中最大的数 4 被看作是 1，其余的数均看作 0，则多重集变为 00000111，此时可以借鉴 “优先移动最大数”思想，将 1 向左移动，当第一个 1 向左移 动以后，产生排列 00001011，此时借鉴 “相同元素尽量靠拢”的思想，将第二个 1 向左 移动，直到所有的 1 都靠拢到最左端，产生 11100000 排列，也即第（56）个排列： 44411223。在这个过程中，0 之间的相对位置保持不变，也即 11223 之间的相对位置保持 不变。 此时，我们再把集合中次大的元素 3 向左移动一个位置，得到排列 44411232，然后再 将最大元素 4 看作 1，其它元素看作 0，得到 11100000。再将这几个 1 依照“相同元素尽 量靠拢”的思想向右移动，直至移动到最右端 00000111，即得到第（112）个排列： 厦门大学本科毕业论文 13 11232444。 余下的排列过程和以上过程类似，这里就不再一一阐述。总之，Constant Time 算法运 用“优先移动最大数”思想；同时把集合中最大数看作 1，其它数都看作 0，使之成为可 以处理多重集全排列的执行效率很高的一种算法。经过模拟我们证明了它的速度虽然不及 TWDRI 算法，但与其它几种产生多重集排列的算法相比较仍不失为一种效率很高的算法。 因此在本文中对其应该加以介绍。 2.32.3 应用应用 扑克牌的洗牌就是一个对 54 张不同的牌进行排列的过程。当今最前沿的 DNA 计算机 中也有多重集排列的应用，Leonard M. Adelman 在解决“旅行售货员问题(Traveling Salesman Problem)”时，对城市编码的映射空间便是由四个碱基 ATCG 的组合排列构成58。 在密码学中排列有着更为广泛的应用。例如，当明文空间 P 等于密文空间 C 时，那么加密 函数 E 就是集合 P 上的一个置换。也就是说，当明文空间等于密文空间时，则每个加密函 数仅仅是对明文空间的元素的一个重新排列(置换) 59。密码的破译中需要进行大量的组合 排列工作。 厦门大学本科毕业论文 14 第三章第三章 TWDRITWDRI 3.13.1 算法流程图算法流程图 图 3-1 TWDRI 算法主要流程图 3.23.2 算法思想算法思想 判断输入字符串总的字符个数 N 是否等于字符串中不同字符的个数 k。若相等则表明 字符串中每个字符重复出现的次数均为 1 次，调用 Purepermutation (N-1,0) 这一函数；若 不相等则表明字符串中有重复出现多次的字符，即是多重集，我们调用 MultisetPermutation (N-1,0)。在调用 MultisetPermutation (N-1,0)函数的过程中，我们也要随 时检查总的字符个数 N 是否等于字符串中不同字符的个数 k，若相等则调用 厦门大学本科毕业论文 15 Purepermutation (N-1,0)，是一个嵌套调用的过程。 3.33.3 例子例子 算法的具体过程是一个深度优先遍历的过程，以下是对于输入1，2，3，3采用 TWDRI 算法深度优先遍历产生全排列的过程。 1 1 2 23 31 1 3 3 2 2 10 1 19 14 11 3 3 2 1 1 3 3 3 3 34 3 3 3 31 1 7 9 5 6 8 3 3 3 3 1213 2 2 3 3 16 15 2 2 3 3 17 18 1 1 2 2 3 3 21 1 1 3 3 22 23 24 20 1 1 2 23 3 28 26 3 3 27 2 2 29 25 3 3 2 2 33 1 1 31 30 2 21 1 34 32 图 3-2 1、2、3、3 的全排列产生过程 3.43.4 时间复杂度分析时间复杂度分析 排列问题的一个特点就是输出规模受输入规模的影响极大。我们假设计算机进行一次运 算就能给出一个排列(实际的算法不可能做到这点)。对于一台运算速度为百万次每秒的计算 机，给出 10 个元素的集合的所有 10！= 3,628,800 个排列只需几秒钟的时间，而给出 18 个 元素的集合的所有 18！= 6,402,373,705,728,000 个排列则需要几年。就算是当前最快的计算 机，其运算速度达到万亿次每秒，要计算出大于 20 个元素的集合的所有排列在时间上也显 得不太可能。在科学研究中确实可能遇到较大规模的排列需求，除了配置高性能的计算机外 找到一个高性能的排列算法就显得非常必要。 厦门大学本科毕业论文 16 表 3-1 不同性能计算机在各种输入规模下进行排列所需时间 N排列的个数排列的个数百万百万/秒秒十亿十亿/秒秒万亿万亿/秒秒 103628800 1139916800几秒 12479001600几分钟 136227020800几小时几秒 1487178291200天分钟 151307674368000几周几分钟 1620922789888000几个月几小时几秒 17355687428096000几年几天几分钟 186402373705728000几个月几小时 19121645100408832000几年几天 202432902008176640000月 算法的计算时间 T(n)满足： （3-1） 12 3 (1)(3) ( ) (3) nT nC nCn T n Cn 输入规模为 n3 的问题可由 n 个输入规模为 n-1 的子问题构成。是对子问题 12 C nC 结果进行分解和合并的花费，其中、为常数。当 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 C nC 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-3 的递归树 12 ( )(1)T nnT nC nC 从树的根结点开始,根有 n 个分支，第二层的每个节点有 n-1 个分支，一直到倒数第二 层的每个节点有 2 个分支，共 n+1 层。树的第一层有 1 个节点，第二层有 n 个节点，以下 微不足道的时间微不足道的时间 漫长的等待漫长的等待 厦门大学本科毕业论文 17 各层依次节点数为 n(n-1)、n(n-1)(n-2),最后一层为 n！个。 接下来分析在每层的花销。新算法的最大特点在于随着递归层数的增加子问题的取值 空间不断缩小，因此在每个节点上对子问题的分割和合并的花费也从第一层的到 12 C nC 最后一层的不断下降。 12 1CC 本文的算法无需到达树结构的最后一层，而在倒数第三层时便能输出排列。因为在递 归树中一层节点的数目与其以上所有祖先节点的数目之和相近，所以最低两层的排除能带 来性能的提高。 总的时间花费有： 121212 ( )()(1)(2)* (1).T nC nCC nC nC 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 （4-2） 123 5171 ()() ! 266 C eC eCn 对于输入元素个数为 n 的全排列问题，其输出的规模为 n！。因此时间复杂度中的 n！是由问题本身固有的内在特点所决定的。本文算法的时间复杂度最终可以表示为 Cn！(C 为常数)，即从渐进意义上已达到排列问题时间复杂度的理论下界。 厦门大学本科毕业论文 18 第四章第四章 测试模型测试模型 Takaoka 和 Violich 在其论文10中仅仅利用了两个非常简单的多重集例子（3,3,3,3,3 和 2,3,5,2,3）就拿他们的算法与 Korsh and LaFollette9的算法进行比较分析，显然，这 种比较方法是相当没有说服力的。为了全面客观的比较各个算法的性能，我们需要对随机 输入长度为 N 的字符串的所有情况进行测试。一个输入的产生可以看成是从 N 个字符中 每次抽取 1 个字符填满 N 个有序格子。每个格子都有 N 种字符可选，所有共有 NN种输入 情况。 然而我们不必测试所有的 NN种输入，因为其中有些输入的排列时间是相同的。以长 度 4(N4)为例，显然输入“AAAA”和“BBBB”进行排列时间相同，输入“AABB”, “CCDD”和“BCBC”的排列时间也是一样的。这样我们就可以对所有的输入情况进行 分类，把那些具有相同排列时间的输入划分到一类中。到时我们只需测试每类中的一个输 入的排列时间 t，再将时间 t 乘以该类的输入个数 cd就可以得到该类所有输入情况的排列 时间 td。 假定一个输入中有 k 个不同的字符，每个字符的个数分别为 n0, n1, , nk-1，显然，N = n0 + n1 + nk-1。不失一般性，我们假定 D 为 n0, n1, , nk-1的不同拆分数，其中 n0n1nk-1 并且 N = n0 + n1 + nk-1。此时，对于长度为 N 的字符串的所有可能 NN 种输入，就分成了 D 种不同的类别。我们用来表示 D 种分类中的 ,0,1,2,1 ,., d dddd k nnnn 不同组合，其中，d = 0, 1, , D-1.对于每一种分类，它们有相同的排列时间，即 td ，其中， d = 0, 1, , D-1。 对于一个固定的 d 值，我们用 rd来表示中不同数字的个数， ,0,1,2,1 ,., d dddd k nnnn 用来分别记录每个 rd值的个数。表 4-1 显示了当 N=4 时分别带有 ,0,1,1 ,., d ddd r mmm 一个代表性例子的 5 种分类。 表 4-1 当 N=4 的 NN种输入的 5 种分类 d Representativ e kd ,0,1,1 ,., d ddd k nnn ,0,1,1 ,., d ddd r mmm td 00000141t1 1000123, 11, 1t2 厦门大学本科毕业论文 19 2001122, 22t3 3001232, 1, 11, 2t4 4012341, 1, 1, 14t5 对于 N N种可能输入的平均排列时间为： 1 0( ) D d d probability of group d t 11 1 , 000 (!/!)(!/!)/ dd d rk D kN Ndd jd jd djj CkmNntN 1 1 1 , 000 (!/)()/!)(!)( ! d d k r D d kN dd Nd jd j djj NCnm Nkt 例如，当 N = 4（参见表 4-1） ，随机输入长度为 4 的字符串的平均排列时间为： 03124 0011223344 0,00,01,01,11,01,12,02,02,13,03,13,03,13,24,04,04,14,24,3 ! ! kkkkk NNNNN N C k tC k tC k tC k tC k tN Nmnmmnnmnnmmnnnmnnnn 13224 4043414244 4 1!3!2!2!4!4! 41!4!1!1!3!1!2!2!2!1!2!2!1!1!4!1!1!1!1! CtCtCtCtCt 01234 13993 6416641632 ttttt 厦门大学本科毕业论文 20 第五章第五章 测试结果测试结果 为了将 TWDRI 算法同 11 种已知最快或最新的算法12345678910进行公平公正 的模拟比较，所有的算法都用 C 语言实现，测试选择的字符串从字符 0-9 和 a-j 中选出， 并且运行在相同配置环境中（Pentium 4 CPU 2.93 GHz、1 GB 内存） 。测试主要从两个角 度（速度和内存） ，两大分类（单集算法和多重集算法）进行。 Heap63: 递归交换算法1 Heap63: 非递归交换算法1 Ives 76:非递归交换算法2 JT: Loopless的Johnson-Trotter算法（算法3b） 3 JTLLC03: Jeeve Technologies LLC算法7 KL97: Korsh和Lipschutz常数时间算法4 KL04: Korsh和LaFollette基于数组的少循环算法9 Ruskey 03: Ruskey算法53 Sedgewick02: Sedgewick算法6 Takaoka99: Takaoka 的O(1)算法5 TV06: Takaoka和Violich的算法10 5.15.1 TWDRITWDRI 算法和其它单集排列算法的速度和内存比较算法和其它单集排列算法的速度和内存比较 Ives76 是其它 6 种算法中最快的；而 TWDRI 算法的速度是 Ives76 算法的 1.3 倍。 TWDRI 算法内存花销相对其它算法较少。 厦门大学本科毕业论文 21 表 5-1 TWDRI 和集合排列算法在集合输入下的时间比较 (单位：毫秒) NTWDRI Heap63Heap63 Ives 76JT JTLLC 03Sedgewick02 100 31 16 15 47 844 16 1179 313 281 187 375 9,297 109 12969 3,828 3,625 2,328 4,375 112,203 1,250 1312,438 49,921 46,328 29,546 55,093 1,467,906 16,125 14174,328 700,515 652,594 404,750 756,203 20,814,719 226,234 152,618,969 10,575,796 9,835,578 5,980,734 11,183,750 314,241,031 3,393,328 1641,802,563 167,345,218 157,324,766 94,283,398 175,450,984 Estimate:58d54,275,531 17713,381,937925,327,485 0.00E+00 2.00E+07 4.00E+07 6.00E+07 8.00E+07 1.00E+08 1.20E+08 1.40E+08 1.60E+08 1.80E+08 2.00E+08 10111213141516(N) (Time/ms) TWDRI Heap63Heap63Ives 76JTSedgewick 02 图 5-1 输入无重复的单纯集排列算法时间比较 表 5-2 集合全排列算法的峰值/平均内存比较（单位：KB） NTWDRI Heap63Heap63 Ives 76JTJTLLC03Sedgewick02 10736736748748736736748748736736752752744744 11740740748748736736748748736736752752744744 12740740748748736736748748736736752752744744 13740740748748736736748748736736696368744744 14740740748748736736748748736736696368744744 15740740748748736736688368736736696368744744 16740740736736736736736736736736744744 厦门大学本科毕业论文 22 5.2 多重集算法的时间和内存开销比较多重集算法的时间和内存开销比较 TWDRI 算法在处理多重集问题中，速度至少是其它 5 种算法中任何一个的 3 倍。同时 TWDRI 算法内存开销相对其它算法较少。 表 5-3 多重集排列算法的平均时间对比 (单位：毫秒) NTWDRI KL97KL04Ruskey03Takaoka 99TV06 1117 139 220 52 440 149 12157 1,318 2,036 479 4,202 1,369 131,488 12,695 20,389 4,779 42,175 13,729 1415,402 141,908 218,824 51,654 457,865 146,359 15171,967 1,568,173 2,532,981 595,249 5,234,257 1,684,183 162,041,640 7,411,564 0.00E+00 5.50E+05 1.10E+06 1.65E+06 2.20E+06 2.75E+06 3.30E+06 3.85E+06 4.40E+06 4.95E+06 5.50E+06 1112131415(N) (Time/ms) TWDRIKL97KL04Ruskey 03Takaoka 99TV06 图 5-2 多重集全排列算法的平均时间对比 表 5-4 多重集全排列算法峰值/平均内存比较 (单位：KB) NTWDRI KL97KL04Ruskey03Takaoka 99TV06 11768768813813780780728728788788864864 12772772832832788788732732792792868868 13776776859859792792736736800800876876 14772772897897796796740740812812888888 15784784941941804804748748824824896896 16800800752752 厦门大学本科毕业论文 23 5.3 多重集算法在非重复输入的情况下的时间和内存开销比较多重集算法在非重复输入的情况下的时间和内存开销比较 在非重复输入的情况下，TWDRI 算法的速度是其它 5 种多重集算法中最快算法的 9 倍。 表 5-5 多重集全排列算法在单集输入下的时间比较 (单位：毫秒) NTWDRIKL97KL04Ruskey 03Takaoka 99TV06 10017223463547203 11791,9842,7197666,0162,125 1296923,42234,3758,56572,23425,985 1312,438290,375459,907118,229965,765337,250 14174,3284,026,5786,447,2031,540,51913,477,7194,756,985 152,618,96959,588,18796,547,11024,239,643203,435,62571,755,547 1641,802,563945,043,046Estimate:18d373,710,218Estimate:32d1,162,022,906 0.00E+00 1.50E+08 3.00E+08 4.50E+08 6.00E+08 7.50E+08 9.00E+08 1.05E+09 1.20E+09 1.35E+09 10111213141516(N) (Time/ms) TWDRIKL97KL04Ruskey 03Takaoka 99TV06 图 5-3 输入无重复的多重集全排列算法时间比较 5.4 TWDRI 算法与其它多重集排列算法的比较趋势分析算法与其它多重集排列算法的比较趋势分析 随着问题规模的不断增大，TWDRI 算法速度相对其它算法逐渐提高。 表 5-6 其它多重集全排列算法时间与 TWDRI 时间倍数比 NKL97KL04Ruskey 03Takaoka 99TV06 118.176 12.941 3.059 25.882 8.765 128.395 12.968 3.051 26.764 8.720 138.532 13.702 3.212 28.343 9.226 厦门大学本科毕业论文 24 149.214 14.208 3.354 29.728 9.503 159.119 14.729 3.461 30.438 9.794 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 1112131415 N Multiple KL97KL04Ruskey 03Takaoka 99TV06 图 5-4 其它多重集全排列算法时间与 TWDRI 时间倍数比 厦门大学本科毕业论文 25 第六章第六章 结论结论 通过对五十六篇英文论文的研究，总结出排列算法的一个规律：N 个字符排列问题的时 间复杂度为庞大的 C*N!。其中 C 为常数。由于输出规模之大，对 C 的略微的减小就会对算 法的运行速度产生极大的提高。不断的使 C 逼近于 1，正是无数研究者们不断奋斗的目标。 TWDRI 算法突破了以往只有用换位法才能达到最快速度的思想，以递归处理方式使时间复 杂度中的常数 C 趋向于极小值，获得了极佳的性能。 另外，由于以往对排列算法的性能测算没有一个较合理客观的模型，如 Takaoka 和 Violich 在其论文10中仅以两个简单实例就得出关于运行速度方面的结论，实在令人难以信 服。因此，我们推出了新的计算算法性能的新模型，该模型可以较客观准确的测算出排列算 法的性能，为研究者们提供了一种新的参考标准。 基于排列算法庞大的输出结果，我们计划在将来以并行计算的方式将排列算法在多台计 算机上分布输出，这将使运行时间大大缩减。 厦门大学本科毕业论文 26 致谢语致谢语 感谢我的导师教授，使我有机会参与到这样一个对本科生来讲近乎千载难逢的学术研究 中来。陈老师作为我科研领域里的启蒙老师，为了培养我们倾注了很大的心血。在他的悉心 指导下，我从一个茫然无知的青年慢慢开始寻得一丝科研探索的足迹。栽培之恩，学生已然 铭记于心。陈老师渊博的学识，丰富的研究经验，严谨的治学态度，更是我在以后治学道路 上的榜样。 感谢厦门大学软件学院为此次课题研究提供了一流的软硬件设施；感谢学院的各位领导 对我们这次毕业设计的鼎力支持。正是有了大家的帮助，才使得课题获得了成功。 感谢小组成员：陈燕虹、王流斌、王楠和魏洁同学。在这段毕业设计期间大家彼此无私 的帮助，相互的学习，为我这大学本科的最后时光留下了一段难以忘怀的美好回忆。 厦门大学本科毕业论文 27 参考文献参考文献 1Heap, B. R. Permutations by interchangesJ. Computer J., 1963, 6:293-294. 2Ives, F. M. Feb. Permutation enumeration: four new permutation algorithmsJ. Comm. ACM, 1976, 19: 68-72. 3Sedgewick, Robert. Permutation Generation MethodsJ. ACM Computing Surveys (CSUR), 1977, 9: 137-164. 4Korsh, J. and LipsChutz, S. Generating multiset permutations in constant timeJ. Jour. Algorithms, 1997, 25: 321-335. 5Takaoka, T. An O(1) time algorithm for generating multiset permutationsC. ISSAC 99, Lecture Notes in Computer Science, 1999, 1741: 237246. 6Sedgewick, Robert. Permutation generation methodsR. Dagstuhl Workshop on Data Structures, Wadern, Germany, 2002. 7Jeeve Technologies LLC. Frequently Asked Technical Interview Questions and Answers GuideZ. . , 2003. 8Ruskey, F. Combinatorial GenerationM. Working Version (1j-CSC 425-520), 2003. 9Korsh, J. F. and LaFollette, P. S. Loopless array generation of multiset permutationsJ. The Computer Journal, 2004, 47: 612-621. 10Takaoka, T. and Violich, S. Combinatorial generation by fusing loopless algorithmsC. Conferences in Research and Practice in Information Technology Series, 2006, 168: 6977. 11Fischer, L. L. and Krause, K. C. Lehrbuch der Combinationslehre und der ArithmeticZ. Dresden. 1812. 12Tompkins, C. Machine attacks on problems whose variables are permutationsC. In Proc Symposium in Appl. Math., Numerical Analysts, 1956, vol.6, McGraw-Hill, Inc., N.Y., 195-211. 13Lehmer, D. H. Teaching combinatorial tricks to a computerC. In Proc. of Symposium Appl. Math, Combinatorial Analysis,