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

厦门大学本科毕业论文 第 1 页 共 44 页 多重集的全排列算法研究 摘要 字符串的全排列问题是一个非常有趣的数学问题并且有悠久的历史，本文提出了 一种新的并且经过模拟证明是最快的全排列算法。对于一个长度为 N 的字符串来说，如果 它有 k 个不同的字符，每个字符重复出现的次数分别为：, 当这些数不全为 0 n 1 n 1k n 1 时,我们称其为输入有重复的多重集字符串, 它们的全排列问题也因此被称为多重集字符 串的全排列问题。若=，则每个字符出现的次数均为 1，我们称其排列为输入 0 n 1 n 1k n 无重复的单纯集全排列问题。 对这两种不同的排列，历史上均出现过很多经典算法。如对于单纯集全排列，著名算法 大师 Sedgewick 在其著作“permutation generation methods”3中指出，名为 Heap1的算法是递 归中最快的，而 Ives2算法是迭代中最快的。对于多重集来说，Ruskey8、Constant Time4 算法是比较快的。在这些与之比较的算法中，本文将着重介绍经典的单纯集全排列算法 Ives, Johnson and Trotter 和多重集全排列算法 Constant Time。 与传统的全排列算法或者只产生多重集的全排列或者只产生单纯集的全排列不同，本文 的算法对于输入无重复的单纯集以及输入有重复的多重集字符串均能快速产生正确的全排列。 我们引入一个自然数数组：Mappings，将各个不同的输入字符一对一映射到这个连续的自 然数数组，排列过程中仅对这个自然数组进行操作，在适当的时机对数组元素换位，从而不 断缩小子问题的取值空间，实现无需进行大量判断自动排除重复输出。最后排列的结果根据 自然数与字符对应关系得到。 通过对长度 N=10, 11, 12, 13, 14, 15, 16, 和 17 的输入进行模拟并且和其它 11 种 经典的单纯集全排列算法和多重集全排列算法所用的时间加以比较12345678910，本 文的算法 TWDRI 是速度最快的，在占用内存方面也很有优势，平均内存不到 800K。 此外，我们还介绍了一种对于多重集输入的所有可能排列测试其平均排列时间的算法。 关键词 多重集全排列 全排列的产生 最快 字符串的全排列 厦门大学本科毕业论文 第 2 页 共 44 页 A Research into Multiset Permutation Algorithm Abstract The permutation of a string is an interesting mathematical problem and has a long history. In this paper, I will introduce the TWDRI algorithm, a new algorithm which is different from others. Through our simulation and comparison with other eleven algorithms, we have proved that our algorithm is the fastest algorithm among them. Suppose a string whose length is N. If there are k different characters, each has count, respectively. If all these counts dont equal to 1, we call the string 0 n 1 n 1k n “multiset string”, therefore their permutations are called “multiset permutations.” If = 0 n =, then the count for each character is 1, we call their permutations “pure 1 n 1k n permutations.” Many algorithms were introduced for these two kinds permutations. For the pure permutation, the famous algorithm scholar Sedgewick described in his book “permutation generation methods” that the Heap algorithm1 was the fastest recursive exchange algorithm while Ives2 was the fastest iterative exchange algorithm. For the multiset permutations, Ruskey algorithm8 and Constant Time algorithm4 were two faster algorithms. Among these algorithms, I want to emphasize on the pure permutation algorithms: Ives, Johnson and Trotter; multiset permutation algorithm: Constant Time algorithm since they are more classical than other algorithms. Our algorithm, which is different from other algorithms, can deal with both pure permutations and multiset permutations. We introduce an array called Mappings and map each character inputted to this array. During the process of permutation, we only need to operate on this array and make some changes among the elements of the array. Thus the TWDRI algorithm eliminates unnecessary switches and reduces the loop times in order to speed up the permutation and to reduce memory consumption. We evaluate our permutation time and memory consumption by simulating strings with length N = 10, 11, 12, 13, 14, 15, 16, and 17, respectively and calculate average multiset permutation time for all possible N N inputs with each fixed N above. Also we compare the TWDRI algorithm with eleven other algorithms.12345678910 The 厦门大学本科毕业论文 第 3 页 共 44 页 results show that 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. As to the memory consumption, we also have advantage over other algorithms which consume the memory no more than 800Kb. Whats more, we also introduce an evaluation method to calculate the average time of multiset permutations for all possible inputs N N with each fixed length N. Key words Multiset permutations permutation generation fastest string permutations 厦门大学本科毕业论文 第 4 页 共 44 页 目录目录 第一章 引言 6 11 字符串全排列历史 .6 12 单纯集全排列算法历史.6 13 多重集全排列算法历史 .6 14 本文组织结构 .7 第二章 经典全排列算法的分析 8 21 算法概述 .8 22 Ives 算法 8 23 Constant Time 算法 10 231 Johnson 算法 .11 232 Lehmer 算法 12 233 Constant Time 算法 .14 24 Johnson and Trotter 算法 14 第三章 TWDRI 算法模型及简要介绍17 31 定义 17 311 多重集17 312 单纯集17 32 算法概述 17 321 算法的大致思想18 322 初始化的过程18 323 算法的具体过程18 33 时间复杂度分析 20 34 平均时间的测试模型21 第四章 模拟比较 .23 41 测试模型23 42 多重集算法平均时间和内存耗用测试结果24 43 输入无重复多重集全排列算法时间比较25 44 输入无重复单纯集全排列算法时间比较25 45 多重集算法时间的倍数比27 第五章 应用与总结 .27 51 应用 27 52 研究总结28 53 进一步研究 28 致谢 29 参考文献 30 厦门大学本科毕业论文 第 5 页 共 44 页 Contents Chapter 1 Preface6 11 The History of Permutation.6 12 The History of Pure Permutation6 13 The History of Multiset Permutation .6 14 The Structure of This Paper .7 Chapter 2 Analysis of Some Classical Algorithms.8 21 Overview of These Algorithms8 22 Ivess Algorithm8 23 Constant Time Algorithm10 231 Johnsons Algorithm 11 232 Lehmers Algorithm12 233 Constant Time Algorithm.14 24 Johnson and Trotters Algorithm.14 Chapter 3 Brief Introduction to the TWDRI Algorithm17 31 Definition.17 311 Multiset 17 312 Pure Set.17 32 Overview of the TWDRI Algorithm17 321 Overview of the TWDRI Algorithm.18 322 The process of Initialization.18 323 The Illustration of the TWDRI Algorithm18 33 Analysis of Time Complexity 20 34 Average Time Test Model for Multiset Permutations21 Chapter 4 Simulation and Comparison 23 41 Test Model23 42 Average Time and Memory Consumption of Several Multiset Permutations.24 43 Time Comparison of Multiset Permutations for Inputs with Distinct Elements .25 44 Time Comparison of Pure Permutations for Inputs with Distinct Elements25 45 Speed Ratios of TWDRI Algorithm to Other Multiset Permutation Algorithms.27 Chapter 5 Application and Conclusion.27 51 Application27 52 Conclusion28 53 Future Research.28 Acknowledgement29 References.30 厦门大学本科毕业论文 第 6 页 共 44 页 第一章 引言 11 字符串全排列历史 字符串的全排列问题已经有 300 多年的历史了，Donald E. Knuth 在其经典著作计算机 程序设计艺术一书中写道31：“事实上，排列(permutations)问题在计算机领域非常重要。 Vaughan Pratt 提议直接把它们叫做 perms。如果 Pratt 的建议得以实施，那么计算机教科书的 厚度将变得薄一些(相应书的价格也会便宜一点)。 ”虽然 Knuth 语带幽默，但由此可见排列 在计算机领域出现的频率之高。正因为排列问题如此重要，所以一直以来有众多的研究人员 致力于该问题的解决，如引用中所指出的那些文章，都是排列领域中比较经典的算法 123 4568910111213141516171819202122232425262728293031323334353637 383940414243444546474849505152535455 。 12 单纯集全排列算法历史 早期的全排列算法大多是针对无重复输入的情况，针对这些算法，Sedgewick 在其 1977 的著作“permutation generation methods” 3中给出了很好的分析与比较并且加以总结。在文章 中，他指出 1963 年 Heap1的算法是递归中速度最快的，而 1976 年 Ives2的算法是迭代算法 中最快的。其它一些有代表性的算法包括 M. B. Wells 在 1960 年发表的 Recursive methods15 ，1965 年 J. Boothroyd26对其进行了改进，1963 年 S. M. Johnson21 和 H. F. Trotter20 分别 独立提出的 Adjacent exchanges 是一重大突破。在 Johnson-Trotter 算法的基础上 G. Ehrlich33 34引进了减少内部循环的思想得到 “Loopless algorithm”算法，这一算法被 N. Dershowitz35 进一步优化。 13 多重集全排列算法历史 随着时代的发展，无重复输入字符串的全排列已经不能满足实际应用的需要。这时，多 重集字符串的全排列问题便显得很重要了。多重集字符串的全排列经常以字典序排列，另外 一个重要的排列方法是格雷码。所谓的格雷码即相邻两个排列之间仅有一个字母的顺序不同 的排列方法。1997 年，James F. Korsh 和 Paul S. Lipschutz 在 Johnson 算法和 Lehmer 算法的 厦门大学本科毕业论文 第 7 页 共 44 页 基础上，给出了第一个以少循环方式产生 N 个多重集数字的全排列算法4，该算法采用链表 来保存每次产生的排列，并使用指针来对链表进行操作。两年后，Takaoka5使用数组改进 了这一算法。Vajnovszki 在 2003 年研究出一个基于数组的以少循环方式产生多重集全排列 的算法54。在 2004 年，James F. Korsh and Paul S 也提出了一种以少循环方式产生多重集全 排列的算法9。Takaoka and Violich 在 2006 年提出了一个名为 MULTPERM 的算法10，声 称其可以只利用数组在线性空间内产生多重集全排列。 14 本文组织结构 在本文中，我将介绍一种新的多重集全排列算法 TWDRI。在第二部分，介绍一些经典 的单纯集全排列算法 Ives、Johnson and Trotter 算法和多重集全排列算法 Constant Time。第 三章分析 TWDRI 算法模型并简要介绍算法，第四章针对不同的输入进行模拟并与其它 11 种算法在时间和内存方面进行详细比较，第五章阐述全排列的广泛应用以及对本文加以总结。 厦门大学本科毕业论文 第 8 页 共 44 页 第二章 经典全排列算法的分析 21 算法概述 经过与 11 种经典算法进行比较之后，我们发现 Ives 算法是除了 TWDRI 算法之外处理无 重复输入全排列的最快算法,而 Constant Time 算法是处理多重集全排列的最经典算法，因为 它第一个实现了以少循环方式对多重集字符串进行全排列，同时它的执行效率也是比较高的。 1962 年 S. M. Johnson 21 和 H. F. Trotter 20 分别独立提出的相邻换位算法是一个重大的突 破，以后的很多算法都是在他们算法上的改进。因此在本章中，我将对这三种算法给予重点 介绍。 22 Ives 算法 在产生元素 1，2，n 的全排列过程中，Ives 算法每次将第一个元素 1 向右移动一个 位置。当 1 移动到最右端时再将 1 和最左端的元素对换。假设排列最开始的顺序是 1，2，n。经过 n 次移动后，元素 1 又回到了第一个位置。而原来在位置 2,n 的元素 进行了一次循环左移。我们把元素 1 从最左端移动到最右端再移回到最左端看成是 1 的一次 旅行。在元素 1 完成 n1 次旅行后，原来位置在 2,n 的 n1 个元素也完成了 n1 次循 环左移，这时它们各自都回到原来的位置。这个排列就和最开始的第一个排列相同了，必须 加以修改来消除重复排列的产生。接下来对在位置 2，,n-1 的元素 2,n1 重复上面的 操作过程。现在“最左端”和“最右端”分别指位置 2 和位置 n1，而元素 2 是移动的元 素。如果这些元素的排列也产生了重复，那么上面的移动过程又在元素 3,，n2 上继续 进行。下图分别说明了位数为 1,2,3 位时运用 Ives 算法产生全排列的过程。 我们以 3 位输入 ABC 为例来具体说明（如下图 2-1 所示） 。当输入 ABC 后，A 开始向 右移动，移动两次后到达最右端，两次分别产生了 BAC、BCA 这两个排列，也相当于 B、C 分别循环左移一次。在 BCA 中，最右端的 A 和最左端的 B 进行交换，得到 ACB，这 时 A 又开始了向右移动的过程。移动两次分别产生排列 CAB、CBA 后，A 又到达了最右端， 再将 A 与最左端的 C 交换，得到 ABC，和初始输入的排列相同。此时已经产生了所有的全 排列，算法结束。 厦门大学本科毕业论文 第 9 页 共 44 页 该算法伪代码如下： Algorithm Ives Do i=i-1; ci =i; Qi = Pi; While i 1; Do IF ci 1 i = N; x = 0; While ci = = i IF di = = false THEN x = x + 1; ENDIF 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 厦门大学本科毕业论文 第 16 页 共 44 页 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-8 BCDE 转化成转化成 CBDE 后后 A 向反方向移动向反方向移动 从图 2-9 可以看出 N 个元素的排列网络中被框起来的部分构成了 N-1 个元素的排列网 络。也可以看成是在 N-1 个元素的排列网络中插入第 N 个元素从左到右的移动或是从右到 左的移动便得到 N 个元素的排列网络。 厦门大学本科毕业论文 第 17 页 共 44 页 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-92-9 不同位数的全排列过程不同位数的全排列过程 第三章 TWDRI 算法模型及简要介绍 厦门大学本科毕业论文 第 18 页 共 44 页 31 定义 311 多重集 对于一个长度为 N 的字符串来说，如果它有 k 个不同的字符，每个字符重复出现的次 数分别为：, ， 当这些数不全为 1 时, 我们称其为输入有重复的多重集字符串, 0 n 1 n 1k n 它们的全排列问题也因此被称为多重集字符串的全排列问题。 312 单纯集 对于一个长度为 N 的字符串来说，如果它有 k 个不同的字符，每个字符重复出现的次 数分别为：, , 若= = ，则每个字符出现的次数均为 1，我们称其排 0 n 1 n 1k n 0 n 1 n 1k n 列为输入无重复的单纯集全排列问题。 32 算法概述 图图 3-13-1 主要流程图主要流程图 N：总的字符个数； 厦门大学本科毕业论文 第 19 页 共 44 页 k: 字符串中不同字符的个数。 321 算法的大致思想 首先输入一个字符串，然后对其进行初始化，判断总的字符个数 N 是否等于字符串中 不同字符的个数 k。若相等则表明字符串中每个字符重复出现的次数均为 1 次，我们调用 Purepermutation (N-1,0) 这一函数；若不相等则表明字符串中有重复出现多次的字符，即是 多重集，我们调用 MultisetPermutation (N-1,0)。在调用 MultisetPermutation (N-1,0)函数的过 程中，我们也要随时检查总的字符个数 N 是否等于字符串中不同字符的个数 k，若相等则调 用 Purepermutation (N-1,0)，是一个嵌套调用的过程。 322 初始化的过程 将输入的不同字符映射到一个连续的自然数数组，相同的字符映射到相同的自然数。 例如：输入“0112,” 调用初始化函数 Initialization( ), 得到 Mappings0 = 0, Mappings1 = 1, Mappings2 = 2。初始化的好处是在产生排列的过程中，我们不需要对原字符串进行 移动，只需要对这个自然数组进行操作然后在输出的过程中再将自然数组还原为字符串即可 达到产生全排列的目的。 323 算法的具体过程 算法的具体过程是一个深度优先遍历的过程，以下是对于三个不同的输入采用 TWDRI 算法深度优先遍历产生全排列的过程。 厦门大学本科毕业论文 第 20 页 共 44 页 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-23-2 11、2 2、3 3、33 的全排列产生过程的全排列产生过程 X D AD AXAD X DXXADA 1 6 11 2 4791412 3581013 15 图图 3-33-3 A,A, D,D, XX的全排列产生过程的全排列产生过程 A X X A XX 14 2 5 36 X 7 X 8 图图 3-43-4 多重集多重集A,A, X,X, XX的全排列产生过程的全排列产生过程 厦门大学本科毕业论文 第 21 页 共 44 页 33 时间复杂度分析 算法的计算时间 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 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-5 的递归树的递归树 12 ( )(1)T nnT nC nC 从树的根结点开始,根有 n 个分支，第二层的每个节点有 n-1 个分支，一直到倒数第二层的每 个节点有 2 个分支，共 n+1 层。树的第一层有 1 个节点，第二层有 n 个节点，以下各层依次节点 数为 n(n-1)、n(n-1)(n-2), ,最后一层为 n！个。 接下来分析在每层的花销。新算法的最大特点在于随着递归层数的增加子问题的取值空间不 断缩小，因此在每个节点上对子问题的分割和合并的花费也从第一层的到最后一层的 12 C nC 不断下降。 12 1CC 本文的算法无需到达树结构的最后一层，而在倒数第三层时便能输出排列。因为在递归树中 一层节点的数目与其以上所有祖先节点的数目之和相近，所以最低两层的排除能带来性能的提高。 总的时间花费有： 厦门大学本科毕业论文 第 22 页 共 44 页 121212 ( )()1 (1)(2) (1).T nC nCC nC nC nC n 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! C n nnnnn + 2 111111111 !(.) !(1)!(2)!3!2!1!1!2!3! C n nnn 3 4 n i Ci + 12 11 11111111 !()!() !1!2!1!2!3! nn ii C nC n ini 3 ! 6 n C + 12112 1 1311 () ! !26 n i CC nC nCC n i 3 ! 6 n C + 1212 311 () !(1)! 26 CC n eC nC n 3 ! 6 n C （3-2） 123 5171 ()() ! 266 C eC eCn 对于输入元素个数为 n 的全排列问题，其输出的规模为 n！。因此时间复杂度中的 n！ 是由问题本身固有的内在特点所决定的。本文算法的时间复杂度最终可以表示为 Cn！(C 为 常数)，即从渐进意义上已达到排列问题时间复杂度的理论下界。 34 平均时间的测试模型 为了全面客观的比较各个算法的性能，我们需要对随机输入长度为 N 的字符串的所有 情况进行测试。一个输入的产生可以看成是从 N 个字符中每次抽取 1 个字符填满 N 个有序 格子。每个格子都有 N 种字符可选，所有共有 NN种输入情况。 然而我们不必测试所有的 NN种输入，因为其中有些输入的排列时间是相同的。以长度 4(N4)为例，显然输入“AAAA”和“BBBB”进行排列时间相同，输入“AABB”, “CCDD”和“BCBC”的排列时间也是一样的。这样我们就可以对所有的输入情况进行分 类，把那些具有相同排列时间的输入划分到一类中。到时我们只需测试每类中一个输入的排 列时间 t，再将时间 t 乘以该类的输入个数 cd就可以得到该类所有输入情况的排列时间 td。 下面将介绍分类的过程：分类的过程可以抽象为对正整数 N 的分拆。正整数 N 的一个分拆 厦门大学本科毕业论文 第 23 页 共 44 页 是 N 作为称作部分的一个或多个正整数的无序和的一种表示。由于部分的顺序是不重要的， 因此我们总可以排列这些部分使得它们的顺序从最大到最小。1，2，3，4 和 5 对应的分拆 为：1；2，1+1；3，2+1，1+1+1；4，3+1，2+2，2+1+1，1+1+1+1 以及 5，4+1，3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。 N 的一个分拆有时候写成 21 2 1 n aaa N （3-3） 其中为非负整数，该数等于值为 i 的部分的个数(这个表达式是纯符号性的；它的项既 i a 不是指数式，表达式也不是一个乘积)。当被写成式（3-3）的形式时，若0，则项通 i a i a i 常被省略，使用这个记号，4 的分拆为： 41，3111，22，2112，14 的每种 21 2 1 n aaa N 形式对应一种分类。这 5 种分拆就对应长度为 4 的随机输入的 5 种分类： 表表 3-1 长度为长度为 4 的拆分举例的拆分举例 dOne instance 1 n i i a td 141AAAA1(A)t1 23111AAAB2(AB)t2 322DDCC2(DC)t3 42112AABC3(ABC)t4 514ABCD4(ABCD)t5 某类 21 2 1 n aaa N 中如果有项，则该类有个重复出现 i 次的字符。显然各项的 i a i i a i a 和 A(A=)就是构成一个输入字符串的不同字符的个数。 1 n i i a 我们还需要计算每种分类包含的输入情况的个数。还是以长度 4 为例，不失一般性假设 组成输入字符串的字符集合为A，B，C，D。每种分类各项的和 A 代表组成该类一个输 i a 入情况的字符个数，而从字符集合中选取 A 个字符有种选法。表一第 4 行 2112的 A N C A=1+2=3，所以共有=4 种选择 ABC，ABD，ACD，BCD。对于一种选择如 ABC 我们还 3 4 C 要考虑哪个字符重复出现 2 次，A 出现 2 次得到 AABC，B 出现 2 次得到 BBAC，C 出现 2 次得到 CCAB。所以要对每种选择的字符进行排列，有排列个数 厦门大学本科毕业论文 第 24 页 共 44 页 =3。AABC，BAAC 和 BACA 也是不同的，个数为= 1 !/ N i Aai 3!/(1! 2!) 11 !/( !) a N i jk Ni =12。 4!/(2!1!1!) 每个分类中输入情况的个数为： （3-4） 111 (!/) (!/( !) d a NN i A dNd ijk cCAaNi i 至此我们可以得到平均时间的计算公式： （3-5） / N dd TctN 第四章 模拟比较 41 测试模型 我们将算法思想用 C 语言加以实现，并和其它 11 种算法一起在配置为奔腾 4，CPU 主 频为 2.93GHz，内存为 1GB 的电脑上运行。也就是说所有的比较都是在同一环境下进行的， 保证了比较的公平性。 输入要求为 09 十位数字和 AZ 26 个字母，我们测试了 10 位到 17 位的输入，输入为 数字和字母的组合且每个字符的重复次数均为一次。以下是与我们比较的其它 11 种算法： Heap63: 递归交换算法1 Heap63: 迭代交换算法1 Ives 76: 迭代交换算法2 JT: 少循环的Johnson-Trotter算法（算法3b）3 JTLLC03: Jeeve Technologies LLC算法7 KL97: Korsh和Lipschutz常数时间算法4 KL04: Korsh和LaFollette基于数组的少循环算法9 Ruskey 03: Ruskey算法53 Sedgewick02: Sedgewick算法6 厦门大学本科毕业论文 第 25 页 共 44 页 Takaoka99: Takaoka 的O(1)算法5 TV06: Takaoka和Violich的算法10 42 多重集算法平均时间和内存耗用测试结果 表4-1和图4-1显示了如果按照平均时间的测试模型来测试，我们的TWDRI算法比最快的 多重集全排列算法快了三倍，表4-2显示了TWDRI算法的内存消耗量相对来说是比较低的。 表表 4-1 多重集全排列算法的平均时间多重集全排列算法的平均时间 (单位：毫秒单位：毫秒) 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 图图4-1 多重集全排列算法的平均时间比较多重集全排列算法的平均时间比较 表表 4-2 多重集全排列算法的峰值多重集全排列算法的峰值/平均内存比较平均内存比较 (单位单位: KB) NTWDRI KL97KL04Ruskey03Takaoka 99TV06 11768768813813780780728728788788864864 12772772832832788788732732792792868868 厦门大学本科毕业论文 第 26 页 共 44 页 13776776859859792792736736800800876876 14772772897897796796740740812812888888 15784784941941804804748748824824896896 16800800752752 43 输入无重复多重集全排列算法时间比较 表 4-3 和图 4-2 显示出对于输入 1017 位无重复的字符串来说，TWDRI 算法比其它五 种多重集全排列算法快了近九倍。 表表 4-3 输入无重复的多重集全排列算法时间比较输入无重复的多重集全排列算法时间比较 (单位：毫秒单位：毫秒) NTWDRIKL97KL04Ruskey 03Takaoka 99TV06 1 0 017223463547203 1 1 791,9842,7197666,0162,125 1 2 96923,42234,3758,56572,23425,985 1 3 12,438290,375459,907118,229965,765337,250 1 4 174,3284,026,5786,447,2031,540,51913,477,7194,756,985 1 5 2,618,96959,588,18796,547,11024,239,643203,435,62571,755,547 1 6 41,802,563945,043,04 6 Estimate:18 d 373,710,21 8 Estimate:32 d 1,162,022,90 6 1 7 713,381,93 7 厦门大学本科毕业论文 第 27 页 共 44 页 图图 4-2 输入无重复的多重集全排列算法时间比较输入无重复的多重集全排列算法时间比较 44 输入无重复单纯集全排列算法时间比较 表格4-4和图4-3显示出当输入为1016位不同字符时，TWDRI算法比其它六种输入无重复 的单纯集全排列算法快了最少1.3倍。表格4-5显示出TWDRI算法的内存消耗量相对来说是比 较低的。 表表 4-4 输入无重复的单纯集全排列算法时间比较输入无重复的单纯集全排列算法时间比较 (单位：毫秒单位：毫秒) NTWDRI Heap63Heap63 Ives 76JT JTLLC 03Sedgewick0 2 1 0 0 31 16 15 47 844 16 1 1 79 313 281 187 375 9,297 109 1 2 969 3,828 3,625 2,328 4,375 112,203 1,250 1 3 12,438 49,921 46,328 29,546 55,093 1,467,906 16,125 1 4 174,328 700,515 652,594 404,750 756,203 20,814,719 226,234 1 5 2,618,969 10,575,796 9,835,578 5,980,734 11,183,750 314,241,031 3,393,328 1 6 41,802,563 167,345,21 8 157,324,76 6 94,283,39 8 175,450,98 4 Estimate:58 d 54,275,531 1 7 713,381,93 7 925,327,48 5 厦门大学本科毕业论文 第 28 页 共 44 页 图图 4-3 输入无重复的单纯集全排列算法时间比较输入无重复的单纯集全排列算法时间比较 表表 4-5 单纯集全排列算法的峰值单纯集全排列算法的峰值/平均内存比较平均内存比较 NTWDRI Heap63Heap63 Ives 76JTJTLLC 03Sedgewick02 10736736748748736736748748736736752752744744 11740740748748736736748748736736752752744744 12740740748748736736748748736736752752744744 13740740748748736736748748736736696368744744 14740740748748736736748748736736696368744744 15740740748748736736688368736736696368744744 16740740736736736736736736736736744744 45 多重集算法时间的倍数比 表 4-6 和图 4-4 显示了输入字符串位数为 1115 位时其它 11 种算法所用时间与我们的 TWDRI 时间的倍数比。 表表 4-6 其它多重集算法时间与其它多重集算法时间与 TWDRI 时间的倍数比时间的倍数比 NKL97KL04Ruskey 03Takaoka 99TV06 118.17612.9413.05925.8828.765 128.39512.9683.05126.7648.720 138.53213.7023.21228.3439.226 厦门大学本科毕业论文 第 29 页 共 44 页 149.21414.2083.35429.7289.503 159.11914.7293.46130.4389.794 图图 4-4 其它多重集算法时间与其它多重集算法时间与 TWDRI 时间的倍数比时间的倍数比 第五章 应用与总结 51 应用 扑克牌的洗牌就是一个对 54 张不同的牌进行排列的过程。当今最前沿的 DNA 计算机 中也有多重集排列的应用，Leonard M. Adelman 在解决“旅行售货员问题(Traveling 厦门大学本科毕业论文 第 30 页 共 44 页 Salesman Problem)”时，对城市编码的映射空间便是由四个碱基 ATCG 的组合排列构成。在 密码学中排列有着更为广