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

厦门大学本科毕业论文 I 本科毕业论文本科毕业论文 (科研训练、毕业设计) 题题 目：多重集的全排列算法研究目：多重集的全排列算法研究 姓 名： 学 院：软件学院 系：软件工程系 专 业：软件工程 年 级： 学 号： 指导教师（校内）： 职称： 年 月 厦门大学本科毕业论文 II 多重集的全排列算法研究多重集的全排列算法研究 摘要摘要 全排列问题是一个经典的数学问题，可分为一般无重复输入的单重集排列问题和重 复输入的多重集（Multiset）排列问题。在多重集中，同一个元素可多次出现，而在单重集 中，一个元素有且仅有出现一次。本文提出一种新的全排列产生算法（TWDRI） 。该算法不 仅能处理一般的单重集排列问题，而且能处理更为复杂的多重集排列问题，同时，TWDRI 算法适用于各种不同字符的输入情况，具有广泛的通用性。在此，我们进行了大量的模拟， 测试了从 10 位到 17 位的输入情况，并与 11 种世界上已知的最快或最新的算法1234567 8910进行详细的比较。模拟比较结果证明，本文提出的算法表现出相当优秀的时间和空间 性能：在处理多重集问题上，速度是现存已知算法的 3 倍，内存开销也仅仅在 800K 以下。 同时，本文也首次提出一种科学的计算方法，用于评估随机输入 N 位长度的多重集排列产 生的平均时间，具有历史创新性。 关键词关键词 多重集 排列 算法 厦门大学本科毕业论文 III A Research into Multiset Permutation Algorithm Abstract We introduce TWDRI algorithm, the fastest new permutation technique for multiset permutations. A multiset is a set for which repeated elements are considered. The multiset permutation is a mathematical model. 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 algorithms12345678910 in detail. The comparisons show our algorithm is three times faster than the fastest of them for multiset 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 algorithm 厦门大学本科毕业论文 4 目录目录 第一章第一章 引言引言6 6 第二章第二章 研究背景研究背景7 7 2.12.1 多重集排列的相关定义多重集排列的相关定义 .7 2.22.2 全排列问题的研究历史全排列问题的研究历史 .7 2.2.1 单重集排列问题的研究历史 .8 2.2.2 多重集排列问题的研究历史 .8 2.32.3 历史上的主要经典算法历史上的主要经典算法 10 2.3.1 Heap 递归算法10 2.3.2 Ives 非递归算法11 2.3.3 基于格雷码顺序的多重集排列算法 13 第三章第三章 TWDRITWDRI 算法的基本模型算法的基本模型 1515 3.13.1 主要流程图主要流程图 15 3.23.2 算法产生排算法产生排列列的过程的过程 15 3.33.3 算法时间复杂度算法时间复杂度 16 3.43.4 算法的通用性和创新性算法的通用性和创新性 18 第四章第四章 模拟比较模拟比较2020 4.14.1 多重集排列的平均时间计算模型多重集排列的平均时间计算模型 20 4.1.1 基于随机输入的平均时间计算模型.20 4.1.2 计算模型的推导过程.20 4.1.3 平均时间计算公式.22 4.24.2 模拟比较结果模拟比较结果 23 4.2.1 多重集算法的时间和内存开销比较.23 4.2.2 多重集算法在非重复输入的情况下的时间比较.25 4.2.3 TWDRI 算法与其它单重集排列算法的时间和内存开销比较.25 4.2.4 TWDRI 算法与其它多重集排列算法的比较趋势分析.27 第五章第五章 结论结论2828 致谢语致谢语2929 参考文献参考文献3030 厦门大学本科毕业论文 5 Contents Chapter1 Introduction.6 Chapter2 Background7 2.1 The Related Definition of Multiset Permutation .7 2.2.1 The History of Pure Permutation .8 2.2.2 The History of Multiset Permutation8 2.2 The Study History of Multiset .7 2.3 Classical Algorithm.10 2.3.1 Heaps Recursive Algorithm.10 2.3.2 Ivess Iterative Algorithm.11 2.3.3 Multiset Permutation Algorithm Based on Grad-Code Order13 Chapter3 The TWDRI Model.15 3.1 Main Flowchart.15 3.3 The Process of Permutation Generation.15 3.3 Time Complexity.16 3.4 Universality and Innovation 18 Chapter4 Simulation and Comparison.20 4.1 Computing Model for Evalueation Mutliset Permutation20 4.1.1 Computing Model Based on Random Input.20 4.1.2 Derivation of Computing Model20 4.1.3 Computing Model for the Average Time of Mutliset Permutation22 4.2 The Result of Simulation and Comparison 23 4.2.1 Comparison of Average Time and Memory of Mutliset Permutation .23 4.2.2 Comparison of Average Time and Memory of Mutliset Permutation with Distinct Elements25 4.2.3 Comparison of Average Time and Memory of Pure Permutation .25 4.2.4 Speed Rations of TWDRI Algorithm to Others.27 Chapter5 Summary28 Acknowledgement 29 References .30 厦门大学本科毕业论文 6 第一章第一章 引言引言 全排列问题是一个经典的数学问题，有着悠久的历史。全排列问题的产生可以追溯到 十六世纪五十年代，早在 1960 年就有这一领域算法的总结性文章出现1112。一代算法宗师 Donald E. Knuth 在其经典著作计算机程序设计艺术13一书中写道：“事实上，排列 (permutations)问题在计算机领域非常重要。Vaughan Pratt 提议直接把它们叫做 perms。如果 Pratt 的建议得以实施的话，那么计算机教科书的厚度将变得薄一些（相应书的价格也会便宜 一点） ” 。虽然 Knuth 语带幽默，但由此可见排列在计算机领域出现的频率之高。正是因为排 列问题如此重要，所以在过去的几十年里，一直以来有众多的研究人员致力于该问题的研究。 本文正是在这种历史背景下孕育而生的。 本文提出了一种新的快速产生全排列的算法（TWDRI） ，它不仅能处理一般的单重集排 列问题，而且能处理更为复杂的多重集排列问题。其通用性和快速性对于全排列在实际生活 中的应用具有深刻的意义，例如密码学领域对输入的一些数字或字符产生其对应的密码，生 物医学领域 DNA 所有的可能排列等等。 本文的第二章将详细讲述多重集的排列问题，第三章将给出 TWDRI 算法的基本模型， 第四章将首次提出基于随机输入的多重集排列的平均时间计算模型，并与 11 种世界上已知 的最快或最新的算法经行模拟比较，从而得出结论：TWDRI 算法是当今世界上处理多重集 问题的最快算法。 厦门大学本科毕业论文 7 第二章第二章 研究背景研究背景 2.12.1 多重集排列的相关定义多重集排列的相关定义 定义定义 1 1（多重集的长度 N） 我们把 N 个字符长度的字符串 S 看成一个多重集，字符串 S 包含 k 个不同的字符，每个字符的个数分别为 n0, n1, , nk-1。显然，N = n0 + n1 + nk-1。 当 N=k 时，我们把此时的多重集称为单重集，因为此时 n0 = n1 = nk-1 = 1，每个不同字符 的个数有且仅有一个。即我们一般意义上的无重复输入。 定义定义 2 2（重复个数 n0, n1, , nk-1） 对于长度为 N，有 k 个不同字符，每个字符个数分别 为 n0, n1, , nk-1的多重集，我们把 n0, n1, , nk-1 称为每个字符的重复个数。 定理定理 1 1（多重集的排列数） 令 S 是长度为 N 的多重集，它有 k 个不同的元素，每个元 素的重复数分别为 n0, n1, , nk-1，那么，多重集 S 的排列数=，其中 N = n0 + n1 011 ! !.! k N n nn + 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。 2.22.2 全排列问题的研究历史全排列问题的研究历史 大部分科学家，特别是计算机和数学领域的专家，当他们需要列举所有可能性并核对所 希望结果的时候，经常会碰到这样或那样的问题，事实上，这些问题都属于全排列问题。单 重集排列和多重集排列在很多领域都有广泛的应用，例如 DNA 排序，密码学，运筹学，电 路设计，统计学和化学领域等等。 科学家们对于单重集排列和多重集排列的研究，已经有 300 多年历史了123456789 10 厦门大学本科毕业论文 8 111213141516171819202122232425262728293031323334353637383940414243444546 474849505152535455。对于单重集排列的产生算法，百年来可以说不胜枚举，遗憾的是， 对于多重集排列，相关的算法就屈指可数，而对于两种排列都适用的算法，百年来更是少之 又少。与此同时，大部分算法在分析方面都缺乏详细的模拟和比较，例如计算平均时间部分。 最近，Takaoka 和 Violich 在其论文10中仅仅利用了两个非常简单的多重集例子（3,3,3,3,3 和 2,3,5,2,3）就拿他们的算法与 Korsh 和 LaFollette 的算法9进行比较分析，显然，这种 比较方法是相当没有说服力的。 2.2.12.2.1 单重集排列问题的研究历史单重集排列问题的研究历史 科学家们总是在寻求一种尽可能快的算法来产生单重集或多重集排列。关于单重集排列 问题，已知最早的算法于 1605 年在英国教堂产生的6，当时，教堂中的牧师用它来计算几 口大钟不同的撞击顺序，以此产生各种不同的音乐效果。其后，具有代表性的算法包括 M. B. Wells12的递归算法和 S. M. Johnson22，H. F. Trotte21具有突破意义的邻位交换法。1973 年，G. Ehrlic 提出了一种减少内层循环的 loopless 算法33，随后，不少研究者紧接着又发展 了这一算法14172432363739。另外两种算法是字典序法11161923263031和随机排列法11 13242528。一代算法大师 Robert Sedgewick 曾于 1977 年对各种单重集排列的产生算法做了 一个全面而深刻的研究3，其中，Sedgewick 指出，Heap1是当时最快的递归交换算法，同 时，Ives2是最快的非递归交换算法。在 2002 年，Sedgewick 又提出了一个 Heap 递归算法 的改进版本6，该算法通过直接排列后三位字符来加快总体排列产生的速度。 2.2.22.2.2 多重集排列问题的研究历史多重集排列问题的研究历史 与单重集排列相比，多重集排列算法的发展起步较晚。多重集的排列顺序通常有两种， 字典顺序和格雷码顺序。所谓的格雷码顺序，即每相邻两个排列之间只有一个数位发生变化。 F. Ruskey 认为，按照格雷码顺序产生多重集排列的算法是在处理多重集排列问题中最快的 算法8。James F. Korsh 同 Paul S. Lipschutz 在结合 Johnsons 22和 Lehmers algorithms 25算 法的基础上，首次提出了产生多重集排列的 loopness 算法4。在这个新算法中，多重集的排 列是以链表形式产生的，链表中的操作都是由指针来完成，其中包括 O(1)时间的交换操作。 两年后，Takaoka 使用数组改进了这个 O(1)时间的算法5。Vajnovszki54进一步提出了一种 基于数组的少循环算法。2004 年，James F. Korsh 和 Paul S. LaFollette 提出一种新的 loopness 厦门大学本科毕业论文 9 算法9，与以往基于数组的算法不同，这个新算法仅仅需要长度大小的线性存储。Takaoka 和 Violich 于 2006 年又提出一种仅仅使用数组就能在线性空间产生多重集排列的 MULTPERM 算法10，其声称，MULTPERM 算法比 James F. Korsh 和 Paul S. LaFollettede 的算法9更为简单和有效，但是，遗憾的是，他仅仅使用了两个非常简单的多重集例子： 3,3,3,3,3和2,3,5,2,3 10。另外，尽管不少科学家对多重集排列问题都给出了精妙的算法， 但这些算法都始终没有突破通过保存和判断信息来防止重复输出的思维藩篱。 排列问题的一个特点就是输出规模受输入规模的影响极大。我们假设计算机进行一次运 算就能给出一个排列（实际的算法不可能做到这点） 。对于一台运算速度为百万次每秒的计 算机， 给出 11 个元素的集合的所有 11！= 399168 个排列只需几秒钟的时间，而给出 17 个 元素的集合的所有 17！= 355687428096000 个排列则需要几年。就算是当前最快的计算机， 其运算速度达到万亿次每秒，要计算出大于 20 个元素的集合的所有排列在时间上也显得不 太可能。在科学研究中确实可能遇到较大规模的排列需求，除了配置高性能的计算机之外， 找到一种高性能的排列算法就显得非常必要。 表 2-1 不同性能计算机在各种输入规模下进行排列所需时间 N排列的个数排列的个数百万百万/秒秒十亿十亿/秒秒万亿万亿/秒秒 103628800 1139916800几秒 12479001600几分钟 136227020800几小时几秒 1487178291200天分钟 151307674368000几周几分钟 1620922789888000几个月几小时几秒 17355687428096000几年几天几分钟 186402373705728000几个月几小时 19121645100408832000几年几天 202432902008176640000月 微不足道的时间微不足道的时间 漫长的等待漫长的等待 厦门大学本科毕业论文 10 2.32.3 历史上的主要经典算法历史上的主要经典算法 在著名的算法大师 Robert Sedgewick 于 1977 年发表的研究文章中3，他比较了众多关于 单重集排列算法，得到了如下结论， Heap1是最快的递归交换算法，同时， Ives2是最快 的非递归交换算法。这两种算法都是基于交换实现的。而对于多重集排列问题，F. Ruskey 认为，按格雷码顺序产生排列的算法是处理此类问题中最快的算法8。下面，本文将给出以 上三种算法的基本模型和排列产生过程。 2.3.12.3.1 HeapHeap 递归算法递归算法 Heap 算法在处理单重集问题上是最快的的递归算法，它是基于交换实现的，每次产生 一个排列时只交换两个位置上的字符的位置，经过递归，从而得到所有正确的排列。 定义定义 3 3（P数组） Pi是 N 位长度字符串中每一位的字符，i=1,2N。 定义定义 4 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 ci1: i:=i-1 repeat； process； loop if ci 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; 厦门大学本科毕业论文 14 基于格雷码顺序的排列产生结果如图 2-3 和 2-4 所示: A B C A C B C A B C B A B C A B A C 图 2-5 当 N=3 时，基于格雷码的多重集排列算法的排列产生图 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-6 当 N=4 时，基于格雷码的多重集排列算法的排列产生图 厦门大学本科毕业论文 15 第三章第三章 TWDRI 算法的基本模型算法的基本模型 3.13.1 主要流程图主要流程图 TWDRI 算法是一种新的快速的全排列产生算法。该算法能同时解决一般无重复输入的 单重集排列问题和重复输入的多重集（Multiset）排列问题。程序根据输入字符串，自动选 择处理单重集排列问题的 PurePermutation()函数，或者处理多重集排列问题的 MultisetPermutation()函数，从而，既满足了输入字符串的随机性，又达到了快速处理两种不 同集合的排列问题。 图 3-1 是算法其主要流程图： Start Input a string Initialization() N=k PurePermutation(N-1,0)MultisetPermutation(N-1,0) End YN 图 3-1 TWDRI 算法的主要流程图 3.23.2 算法产生排列的过程算法产生排列的过程 为了形象地表示出算法 TWDRI 产生排列的过程，我们通过以下两个例子来具体说明。 厦门大学本科毕业论文 16 图 3-2，图 3-3 分别说明了当输入是多重集 A,X,X 和1,2,3,3时排列产生的过程。其中， 线条上的数字表示排列产生的步骤。 A X X A X X 14 2 5 3 6 X 7 X 8 图 3-2 输入A,X,X的排列产生过程 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-3 输入1,2,3,3的排列产生过程 3.33.3 算法时间复杂度算法时间复杂度 算法的计算时间 T(n)满足： （3- 12 3 (1)*(3) ( ) (3) nT nCnCn T n Cn 厦门大学本科毕业论文 17 1） 输入规模为 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-4 的递归树 12 ( )(1)*T nnT nCnC 从树的根结点开始,根有 n 个分支，第二层的每个节点有 n-1 个分支，一直到倒数第二 层的每个节点有 2 个分支，共 n+1 层。树的第一层有 1 个节点，第二层有 n 个节点，以下各 层依次节点数为 n(n-1)、n(n-1)(n-2),最后一层为 n!个。 接下来分析在每层的花销。TWDRI 算法的最大特点在于，随着递归层数的增加，子问 题的取值空间不断缩小，因此，在每个节点上对子问题的分割和合并的花费也从第一层的 到最后一层的不断下降。 12 *CnC 12 CC 本文的算法无需到达树结构的最后一层，而在倒数第三层时便能输出排列。因为在递归 树中一层节点的数目与其以上所有祖先节点的数目之和相近，所以最低两层的排除能带来性 能上的巨大提高。 总的时间花费有： 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 厦门大学本科毕业论文 18 + 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 （3- 123 5171 ()() ! 266 C eC eCn 2） 对于输入元素个数为 n 的全排列问题，其输出的规模为 n!。因此时间复杂度中的 n！是 由问题本身固有的内在特点所决定的。本文算法的时间复杂度最终可以表示为 C*n!(C 为常 数)，即从渐进意义上已达到排列问题时间复杂度的理论下界。 在大多数时间复杂度的分析中，常数 C 都是对程序中语句行数的计算。为了进行较为 精确的分析,我们采用了和 Ives 相同的方法，即计算程序中的赋值、数值运算、比较和下标 引用的使用次数。 3.43.4 算法的通用性算法的通用性和创新性和创新性 定义定义 9 9（Mappings数组） 对于长度为 N，有 k 个不同字符，每个字符个数分别为 n0, n1, , nk-1的字符多重集，我们引进数组 Mappings来映射 k 个不同字符。k 此时为 Mappings 数组的长度。Mappingsi = ni所对应的不同字符，当 i = 0, 1, 2, , k-1 时。 例如，当输入字符串为“0112”时，我们可以得到： N = 4, k =3, n0 =1, n1 =2, n2 = 1; Mappings0 = 0, Mappings1 = 1, Mappings2 = 2。 同理，当输入字符串为“abbc”时，我们可以得到： 厦门大学本科毕业论文 19 N = 4, k =3, n0 =1, n1 =2, n2 = 1; Mappings0 = a, Mappings1 = b, Mappings2 = c。 显然，对于以上两个例子，虽然输入不同，但是，它们映射到了相同的数字多重集 0,1,1,2。 与已有算法不同，TWDRI 采用了 Mappings数组，将各个不同输入字符一对一映射到 连续的自然数数组，排列过程中仅仅对此自然数组进行操作。由于最后排列的产生是根据自 然数与字符对应关系得到的，这样，既解决了传统的多重集问题，又满足了一般字符的随机 输入，具有广泛的通用性。 更为难得可贵的是，TWDRI 算法没有进行换位，也没有按照格雷码顺序产生排列，在 速度上就超越了原有已知的解决相同问题的最快算法，从而，打破了传统解决单重集排列问 题中最快算法都是基于换位的一般看法，也打破了多重集问题中最快的排列产生方法是基于 格雷码顺序的论断。这对全排列算法的研究来说，无疑是个巨大的突破，具有历史创新性。 厦门大学本科毕业论文 20 第四章第四章 模拟比较模拟比较 4.14.1 多重集排列的平均时间计算模型多重集排列的平均时间计算模型 下面我们将首先给出基于随机输入的平均时间计算模型，并进行推导，从而得出多重集 排列的平均时间计算公式。 4.1.14.1.1 基于随机输入的平均时间计算模型基于随机输入的平均时间计算模型 为了全面客观的比较各个多重集算法的性能，我们需要对随机输入长度为 N 的字符串 的所有情况进行测试。一个输入的产生可以看成是从 N 个字符中每次抽取 1 个字符填满 N 个有序格子。每个格子都有 N 种字符可选，所有共有 N N种输入情况。 然而我们不必测试所有的 N N种输入，因为其中有些输入的排列时间是相同的。以长度 4(N4)为例，显然输入“AAAA”和“BBBB”进行排列时间相同，输入“AABB”, “CCDD”和“BCBC”的排列时间也是一样的。这样我们就可以对所有的输入情况进行分 类，把那些具有相同排列时间的输入划分到一类中，得到 D 种分类。最后，我们只需测试 每类中的一个输入的排列时间 td，再将时间 td乘以该类输入的出现概率，求和，就可以得到 该类所有输入情况的平均排列时间 T，也即： （4-1） 1 0 ( )* D d d Tprobability of group dt 4.1.24.1.2 计算模型的推导过程计算模型的推导过程 下面将利用数论中整数分拆（或称整数剖分）的理论来介绍 N N种输入的分类过程。 事实上，我们可以把分类可以抽象为对正整数 N 的分拆。正整数 N 的分拆是指，把 N 表示为一个或多个正整数的无序和，其中，每一个无序和就是 N 的一个分拆。由于分拆成 的若干个正整数的顺序是不重要的，因此我们总可以排列这些正整数，使得它们的顺序从最 大到最小。例如正整数 4 对应的分拆为 4=4，4=3+1，4=2+2，4=2+1+1，4=1+1+1+1。 简而言之，N 的一个分拆可以写成： 厦门大学本科毕业论文 21 （4- 21 2 1 i aaa iiN （1） 2） (这个表达式是纯符号性的；它的项既不是指数式，表达式也不是一个乘积)。 其中为非负整数，该数等于值为 i 的正整数的个数。当被写成式（4-2）的形式时，若 i a 0，则项通常被省略，使用 这个记号，4 的分拆为：41，3111，22，2112，14。 i a i a i 的每种形式对应一种分类，则正整数 4 的分拆总共有 5 类，具体如下表 21 2 1 i aaa i 4-1 所示： 表 4-1 正整数 4 的分拆 d 字符串举例字符串举例 k= 1 n i i a 141AAAA1 23111AAAB2 322AABB2 42112AABC3 514ABCD4 显然，应用这种分拆的分类思想，我们可以得到，为多重集问题中互不相同的字符 1 n i i a 的个数 k，根据定义 2，每种分类中的各个字符的重复次数 n0, n1, , nk-1也能轻松得出，即 中每个不为 0 的的下标项 i，也因此，此时 n0 n1nk-1 21 2 1 i aaa iiN （1） i a 至此，为了求得每种分类的出现概率，我们还需要计算每种分类包含的输入情况的个数。 还是以长度 4 为例，不失一般性，假设组成输入字符串的字符集合为A,B,C,D，每种分类 中组成该类一个输入的不同字符个数为 k，而从字符集合中选取 k 个字符有种选法。表 4- k N C 1 第 4 行 k=1+2=3，所以共有=4 种选择：ABC，ABD，ACD，BCD；对于一种选择如 3 4 C ABC 我们还要考虑哪个字符重复出现 2 次：A 出现 2 次得到 AABC，B 出现 2 次得到 BBAC，C 出现 2 次得到 CCAB，因此要对每种选择的字符进行排列，有排列个数 =3；当 A 出现 2 次时，AABC，BAAC 和 BACA 也是不同的，排列个 1 !/ N i kai 3!/(1!*2!) 厦门大学本科毕业论文 22 数为=12。所以，当 N=4，k=3，分拆 2112所对应的分类总 11 !/( !) a N i jk Ni 4!/(2!*1!*1!) 共有 4*3*12 种输入情况，其在所有 44种随机输入中所占的概率为 4*3*12/44。 所以，每个分类中所有输入情况的出现概率为： （4- 111 (!/!)(!/( !)/ d a NN i kn Nd ikj probability of group dCkaNiN i 3） 4.1.34.1.3 平均时间计算公式平均时间计算公式 为了方便应用与理解，我们根据以上推导，总结如下： 假定一个输入中有 k 个不同的字符，每个字符的个数分别为 n0, n1, , nk-1，显然，N = n0 + n1 + nk-1。不失一般性，我们假定 D 为 n0, n1, , nk-1的不同拆分数，其中 n0 n1nk-1， 并且 N = n0 + n1 + nk-1。此时，对于长度为 N 的字符串的所有可能 N N种 输入，就分成了 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-2 显示了当 N=4 时N N种输入中 ,0,1,1 ,., d ddd r mmm 分别带有一个代表性例子的 5 种分类。 表 4-2 当N=4 的N N种输入的 5 种分类 d字符串举例字符串举例kd ,0,1,1 ,., d ddd k nnn ,0,1,1 ,., d ddd r mmm td 00000141t1 1000123, 11, 1t2 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 厦门大学本科毕业论文 23 （4- 1 1 1 , 000 (!/)()/!)(!)( ! d d k r D d kN dd Nd jd j djj NCnm Nkt 4） 例如，当N = 4（参见表4-2） ，随机输入长度为 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 4.24.2 模拟比较结果模拟比较结果 借鉴以往大型模拟比较的经验56，我们把 TWDRI 算法同 11 种已知最快或最新的算法 进行模拟比较。为保证比较的的科学性、准确性和公平性，所有的算法都用遵循 ANSI C 标 准的 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: 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 厦门大学本科毕业论文 24 Takaoka99: Takaoka 的 O(1)算法5 TV06: Takaoka 和 Violich 的算法10 4.2.14.2.1 多重集算法的时间和内存开销比较多重集算法的时间和内存开销比较 表 4-3 和图 4-1 说明 TWDRI 算法在处理多重集问题中，速度至少是其它 5 种算法中任 何一种的 3 倍。表 4-4 则说明，相对其它算法而言，TWDRI 算法的内存开销是比较小的。 因此，显而易见的，同各种多重集排列算法相比，TWDRI 算法表现出相当优秀的时间和空 间性能。 表 4-3 多重集排列算法的平均时间比较 (单位：毫秒) NTWDRI KL97KL04Ruskey03Takaoka 99 TV06 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,56 4 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 图4-1 多重集全排列算法的平均时间比较 表 4-4 多重集全排列算法内存的峰值平均值比较 (单位：KB) 厦门大学本科毕业论文 25 NTWDRI KL97KL04Ruskey03Takaoka 99 TV06 11768768813813780780728728788788864864 12772772832832788788732732792792868868 13776776859859792792736736800800876876 14772772897897796796740740812812888888 15784784941941804804748748824824896896 16800800752752 4.2.24.2.2 多重集算法在非重复输入的情况下的时间比较多重集算法在非重复输入的情况下的时间比较 表 4-5 和图 4-2 说明，在非重复输入的情况下，TWDRI 算法的速度是其它 5 种多重集 算法中最快算法的 9 倍。 表 4-5 多重集全排列算法在无重复输入下的时间比较 (单位：毫秒) NTWDRIKL97KL04Ruskey 03Takaoka 99TV06 10017223463547203 11791,9842,7197666,0162,125 1296923,42234,3758,56572,23425,985 1312,438290,375459,907118,229965,76533