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

I 多重集全排列算法研究多重集全排列算法研究 摘要摘要 本文提出一种新的全排列产生算法TWDRI。该算法能同时解决一般的无重复输 入的单集(pure permutation)问题和输入有重复的多重集(multiset permutation)问题，而且适用 于各种不同字符输入情况，具有通用性。与已有算法不同，本文的新算法首先根据输入字符 的频率预排序，再将各个不同输入字符一对一映射到连续的自然数数组。排列过程中仅对该 数组进行操作，在适当的时机对数组元素换位，从而不断缩小子问题的取值空间，无需进行 大量判断就可以自动排除重复输出。最后排列的结果再根据自然数与字符对应关系得到。而 且对于多重集，本文提出了一种新的评估多重集算法性能的方法平均时间(average time of multiset permutations)，对于长度为 N 的输入，由它产生的所有的 NN种情况都进行测试。 我们进行了大量的模拟，测试了从 10 位到 17 位的输入情况，与已知的算法进行了比较123 45678910，本文提出的算法表现出优秀的性能，比已有算法使用更快的时间得到所有排 列结果。 关键词关键词 全排列 多重集 算法 II A Research into Multiset Permutation Algorithm Abstract We introduce a new permutation generation methodTWDRI. It can solve both problems the general non-duplicated input(pure permutation) and the duplicated input(multiset permutation).Besides, it can handle all kinds of different characters input. Compared with the existing algorithms, this new algorithm is based on the frequency of input characters. It sorts the characters first by their frequency then map them to a natural numbers array(Mapping) one-by-one. When generating the permutation, it just manipulates the array element rather than characters. During the process, we delete the array element in order to shrink the value-space of the sub-problem and reduce lots of estimation for avoiding repeated output. At last, we will get the results according the Mapping to transform the natural numbers to the initial characters that we input. For the multiset permutation, we also introduce a new method to estimate such algorithms, which is called Average Time of Multiset Permutation. We evaluate our permutation time and memory consumption by simulating strings from length N = 10 to 17, respectively. We calculate average multiset permutation time for all possible NN inputs with each fixed length N above. We compare our results with the fastest known and/or well- known algorithms12345678910 in detail. And this algorithm shows great performance, it use less time than all the algorithm that we have mentioned. Key words permutation multiset algorithm III 目录目录 第一章第一章 引言引言1 1 第二章第二章 多重集排列的相关定义多重集排列的相关定义3 3 2.12.1 多重集排列的理论基础多重集排列的理论基础 3 3 2.22.2 关于多重集排列的定理关于多重集排列的定理 3 3 第三章第三章 经典字符排列算法分析经典字符排列算法分析5 5 3.13.1 字典序法字典序法 5 5 3.23.2 递增进位制数法递增进位制数法 6 6 3.33.3 递减进位制数法递减进位制数法 8 8 3.43.4 邻位对换法邻位对换法( (格雷码序法格雷码序法) ) 1010 3.53.5 元素增值法元素增值法(N(N 进制法进制法) ) 1111 3.63.6 递归类算法递归类算法 1212 第四章第四章 TWDRITWDRI 算法介绍算法介绍 1515 4.14.1 算法整体流程图算法整体流程图 1515 4.24.2 算法特色算法特色 1616 4.34.3 时间复杂度分析时间复杂度分析 1616 第五章第五章 平均测试模型平均测试模型1919 5.15.1 整数拆分的理论基础整数拆分的理论基础 1919 5.25.2 平均时间测试模型平均时间测试模型 2020 第六章第六章 模拟和比较模拟和比较2222 6.16.1 测试环境与案例测试环境与案例 2222 6.26.2 时间与内存比较时间与内存比较 2222 第七章第七章 应用与总结应用与总结2727 致谢致谢2828 参考文献参考文献2929 IV Contents Chapter 1 Introduction1 Chapter 2 The Definition of Multiset Permutation.3 2.1 The Basic Theoretics of Multiset Permutation.3 2.2 The Theorems of Multiset Permutation3 Chapter 3 Classic Algorithms Analysis5 3.1 Lexicographic Order.5 3.2 Increase by Degrees Carry.6 3.3 Decrease by Degrees Carry8 3.4 Adjacent Exchange(Grad Code)10 3.5 Element Increment11 3.6 Recursion.12 Chapter 4 Introduction of TWDRI.15 4.1 Main Flowchat.15 4.2 Advantage of TWDRI.16 4.3 Analysis of Time Complexity.16 Chapter 5 Average Calculation Model.19 5.1 The Basic Theoretics of Integer Split.19 5.2 Average Time Calculation Model20 Chapter 6 Simulation Environment and Comparison22 6.1 Simulation Environment and Cases.22 6.2 Comparison of Time and Memory22 Chapter 7 Application and Summary 27 Acknowledgments.28 References .29 厦门大学软件学院本科毕业论文 1 第一章第一章 引言引言 在论文最开始，我们有必要明确单集排列问题与多重集排列问题的不同。我们把无重复 输入排列称为“单集”排列或者 Pure Permutation；把无重复输入的集合称为“单集” 。而有 重复输入排列称为“多重集”排列或者 Multiset Permutation；把有重复输入集合称为“多重 集” 。 排列和组合一直是组合数学研究的重点，而多重集的排列又在排列问题中占有很大的比 重，生活中也有很多实际问题与多重集的排列密切相关。有关全排列的问题，早在我们高中 的学习中就有过接触，对于有 N 个完全不同的元素的集合，一共有 N! 个排列。这是通常 意义下的全排列。元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次 数称为该元素的重复度。例如，在多重集合a，a，b，b，b，c，d中，a，b，c，d的重复 度分别为2，3，1，1。因而多重集不能算严格意义上的集合。 很多科学领域，尤其是在计算机和数学会经常遇到字符串全排列问题，需要穷举某个问 题中所有可能出现情况，而且通常情况下是多重集并且要求无重复的输出，对多重集的研究 势在必行。如今全排列不仅在基础数学研究中具有极其重要的地位，在其它的学科如计算机 科学，编码和密码学，统计科学，物理电路设计，化学，生物 DNA 序列等各种领域都有重要 应用。 排列产生的历史可以追溯到十六世纪五十年代，教堂中的牧师计算几口大钟不同的撞击 顺序来产生各式的音乐效果。早在 1960 年就有这一领域算法的总结性文章出现13。图灵奖 获得者 Donald E. Knuth 在其经典著作计算机程序设计艺术一书中写道50：“事实上， 排列(permutations)问题在计算机领域非常重要。Vaughan Pratt 提议直接把它们叫做 perms。 如果 Pratt 的建议得以实施，那么计算机的教科书的厚度将变得薄一些(相应书的价格也会便 宜一点)” 。虽然 Knuth 语带幽默，但由此可见排列在计算机领域出现的频率之高。正是因为 排列问题如此重要，所以一直以来有众多的研究人员致力于该问题的解决。普林斯顿大学计 算机系 Robert Sedgewick 在 1977 年对众多排列产生方法中的经典算法做了分析和比较3，具 有代表性的有 M. B. Wells 在 1961 年发表的 Recursive methods15，1965 年 J. Boothroyd 对其 进行了改进2628；1962 年 S. M. Johnson21和 H. F. Trotter20分别独立提出的 Adjacent exchanges 是一重大突破；Factorial counting 算法是 Johnson-Trotter 算法的另一种实现; 同样 厦门大学软件学院本科毕业论文 2 是在 Johnson-Trotter 算法的基础上 G. Ehrlich3334引进了减少内部循环的思想得到 “Loopless”算法，这一算法被 N. Dershowitz 进一步的优化35；其它还有 F. M. Ives 的 iterative method2; C. Tompkins 和 L. J. Paige 的 Nested cycling12， Peck 和 Schrack 给出了这 一算法的 ALGOL 程序17，还有许多研究人员对这一算法进行改进13142432363739；比较 有影响的算法还有 Lexicographic algorithms1116181922252930与 Random permutations1323 242731。以上这些算法仅能解决无重复输入的单集排列问题。 多重集(Multiset)输入是一个相对较难的问题，不少研究者一直在寻求一个高性能的算法 45384054。多重集的排列一般是按字典序给出。另一种常见的排列顺序是 Gray code，在 Gray code 的排列中相邻的两个排列中仅有两个元素的位置不同。James F. Korsh 和 Paul S. Lipschutz 在 Johnson 算法的基础上结合 Lehmer1324的思想得到第一个使用少循环的多重集 排列产生算法4。在求解多重集排列问题时传统算法为防止重复输出而保存大量纪录信息， 许多研究人员投入精力简化纪录信息的保存和判断验证过程，也产生了许多精妙的算法。但 这些算法都始终没有突破通过保存和判断信息来防止重复输出的思维藩篱。而且大多数发表 的论文都没有一个详细，标准的模拟和比较。最近的论文 Takaoka10与 Korsh9相比较，但 是仅仅使用了3，3，3，3，3和2，3，5，2，3，事实上，仅仅使用几个测试案例是不足 以证明一个算法的优越性能的。 厦门大学软件学院本科毕业论文 3 第二章第二章 多重集排列的相关定义多重集排列的相关定义 2.12.1 多重集排列的理论基础多重集排列的理论基础 定义定义：广义上讲，我们把元素总个数(包括计算重复元素)为N的集合 S 看作是一个多重 集，其中有 k 个不同的元素，它们的重复度分别为 n1 , n2 , , nk 。因此，N = n1+ n2 + nk ，当 N=k 时，S 则成为一个单集，因为 n1 = n2 = nk = 1，它是一个所有元素都不相同的多 重集。 2.22.2 关于多重集排列的定理关于多重集排列的定理 定理定理：对于多重集 S，其元素总个数为 N(包括计算重复元素)，有 k 个不同的元素，其重 复度分别为 n1 ,n2 , nk ，且 N = n1+ n2 + nk 。那么该多重集全排列个数有 (2-1) 12 ! ( ) !.! k N S k n nn 证明：可以将这个问题看作：将 N 个元素的集合划分成 k 个被做标签的盒子 B1 ,B2 , ,Bk 的方式数。其中盒 1 含有 n1个元素，盒 2 含有 n2个元素，盒 k 含有 nk个元素。 首先选取 n1个元素放入第一个盒子，然后从剩下 N-n1个元素中取 n2个元素放入第二个盒 子，然后从剩下的 N-n1-n2个元素中取 n3个元素放入第三个盒子，依此类推，最后将 N-n1- n2-nk-1nk个元素放入第 k 个盒子。由乘法原理，进行选择的总方法数为 ， 121121 132 . . k k NnnnNnnNnN nnnn 即 。 12 ! !.! k N n nn 厦门大学软件学院本科毕业论文 4 由于输入元素个数为 N 的全排列，其输出的规模为 N！。因问题本身固有的内在特点， 其时间复杂度中也必为 O(Cn!)其中 C 为常数（第四部分有时间复杂度的详细分析） 。对于长 度为 17 的字符串，全排列数 17！= 355687428096000，三百万亿种。假设计算机一秒钟可 以输出三百万种，全部输出也要一亿秒钟，也就是说需要 3 年零 2 个月的时间。所以即使 是 20 个元素的集合要计算出的所有排列在人类可以接受的时间内基本上不可能。但是在科 学研究中确实可能遇到较大规模的排列需求，除了配置高性能的计算机外找到一个高性能的 排列算法就显得非常必要。可见对全排列的研究，即使是一点点的提高，都会产生重大的影 响。在我们提出的平均时间方法测试下，本文的算法与所有已存在的 Multiset Permutation 比 较，速度至少是它们的 3 倍；在已经研究多年的 Pure Permutation 领域，本算法也比同类算 法的速度快 0.3 倍之上。 表 1 不同性能计算机在各种输入规模下进行排列所需时间 N排列的个数排列的个数百万百万/ /秒秒十亿十亿/ /秒秒万亿万亿/ /秒秒 103628800 1139916800几秒 12479001600几分钟 136227020800几小时几秒 1487178291200天分钟 151307674368000几周几分钟 1620922789888000几个月几小时几秒 17355687428096000几年几天几分钟 186402373705728000几个月几小时 19121645100408832000几年几天 202432902008176640000月 微不足道的等待微不足道的等待 时间上几乎不可能时间上几乎不可能 厦门大学软件学院本科毕业论文 5 第三章第三章 经典字符排列算法分析经典字符排列算法分析 全排列的生成算法即对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗 漏地枚举出来。由于我们使用 Mapping数组把任何 n 个字符集的排列与 1n 的 n 个数字 一一对应起来，因而就以 n 个数字的排列为例说明几种常见的排列生成方法。 n 个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列 外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从它的前驱经 过变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。 全排列的生成法通常有以下几种： 3.13.1 字典序法字典序法 字典序法中，对于数字 1，2，3，n 的排列，不同排列的先后关系是从左到右逐个比 较对应的数字的先后来决定的。例如对于 4 个数字的排列 1234 和 1243，排列 1234 在前， 排列 1243 在后。按照这样的规定，4 个数字的所有的排列中最前面的是 1234，最后面的是 4321。 字典序算法如下： 设 P 是 1n 的一个全排列: 121111 . jjjkkkn pp ppp ppp pp 经过以下步骤即可得到该排列的后继排列： 1. 从右端开始，找出第一个比右边数字小的数字的序号 j，即 j = maxi |Pi Pj； 3. 对换 Pi，Pk； 4. 再将 Pj+1Pk-1PkPk+1Pn倒置； 这样可以得到排列 P 的下一个排列。 厦门大学软件学院本科毕业论文 6 121111 . jjnkkkj pp ppp ppp pp 例如 839647521 是数字 19 的一个排列。从它生成下一个排列的步骤如下： 1. 自右至左找出排列中第一个比右边数字小的数字 4 2. 在该数字后的数字中找出比 4 大的数中最小的一个 5 3. 将 5 与 4 交换得到 839657421 4. 将 7421 倒置得到 839651247 所以 839647521 的下一个排列是 839651247。 程序代码如下： Private Sub Dict(P( ) As Integer, ByVal n As Integer) Dim i As Integer, j As Integer OutL P i = n - 1 Do While i 0 If P( i ) 0 For i = 1 To n /排列的各位为 0 P(i) = 0 Next For i = 1 To n /从右向左察看排列中为 0 的位 a = m(i) + 1 j = n 厦门大学软件学院本科毕业论文 8 Do While j 0 If P(j) = 0 Then a = a - 1 If a = 0 Then Exit Do /0 的个数决定数字 i 的位置 End If j = j - 1 Loop P(j) = n - i + 1 /将数字 i 放置在指定位置 Next OutL P If MedN(m) Then Exit Do /计算下一个中介数，如果是 000，则全部排列找到 Loop End Sub Private Function MedN(m() As Integer)As Boolean /计算中介数函数 Dim i As Integer, sum As Integer Dim b As Boolean b = False i = n - 1 Do While i 0 m(i) = m(i) + 1 If m(i) 0 OutL P If P(1) = n Then /如果第一位是 n i = 0 Do /从左端开始找出最长的连续递降序列 i = i + 1 If i = n Then Exit Sub Loop Until P(i) n 的时候，程序结束。 以1，2，3的排列为例： 厦门大学软件学院本科毕业论文 12 原始排列是 1 2 3，从它开始，第 3 个元素是 3，3+2=53，5 Mod 3=2，第 2 个元素是 2，2+1=3，所以新排列是 1 3 2。通过元素增值，顺序产生的排列是： 1 2 3，1 3 2，2 2 2 1 1 1 1 1 1 2 1 3，2 2 2 2 2 2 2 2 2，2 3 1 2 2 2 3 3 3 3 3 3，3 1 2，3 2 1 将有重复元素的排列删除掉，余下的就是全部的排列数。 Private Sub Incr(P() As Integer, ByVal n As Integer) Dim i As Integer, j As Integer Do While n 0 OutL P Nextn: P(n) = P(n) + n - 1 /第 n 个元素增值 n-1 For j = n To 2 Step -1 /从后往前检查 If P(j) n Then /如果元素增值后超过 n P(j) = P(j) Mod n /用 n 除它取余数 P(j - 1) = P(j - 1) + 1 /向前一个元素进位 If P(1) n Then Exit Sub /第一个元素值超过 n，则所有排列都找到 End If Next For i = 1 To n - 1 /检查排列中的元素是否重复 For j = i + 1 To n If P(i) = P(j) Then GoTo Nextn /排列中有重复元素，丢弃 Next Next Loop End Sub 3.63.6 递归类算法递归类算法 3.6.13.6.1 回溯法回溯法 回溯法通常是构造一颗生成树。以 3 个元素为例：树的节点有 3 个数据，可取值是 1，2，3。如果某个为 0，则表示尚未取值。初始状态是(0，0，0)，第 1 个元素值可以分别 挑选 1，2，3，因此扩展出 3 个子结点。用相同方法找出这些结点的第 2 个元素的可能值， 如此反复进行，一旦出现新结点的 3 个数据全非零，那就找到了一种全排列方案。当尝试了 所有可能方案，即获得了问题的解答。 厦门大学软件学院本科毕业论文 13 程序代码如下： Private Sub Remo(P() As Integer, ByVal k As Integer) Dim b As Boolean If k = n + 1 Then /如果 kn 则输出一个排列 OutL P Else /否则 For i = 1 To n b = False /重复元素标志置为 False P( k ) = i /第 k 个元素设为 i For j = 1 To k - 1 /检查是否存在重复元素 If i = P( j ) Then /有重复 b = True /设置重复标志为 True j = k - 1 /回溯 End If Next /换一个元素试探 If Not b Then Remo P, k + 1 /无重复，继续递归查找下一个元素 Next End If End Sub 3.6.23.6.2 递归算法递归算法 定义：定义：如果用 P 表示 n 个元素的排列，而 Pi表示不包含元素 i 的排列，iPi表示在排列 Pi 前加上前缀 i 的排列，那么，n 个元素的排列可递归定义为： 如果 n=1，则排列 P 只有一个元素 i 如果 n1，则排列 P 由排列iPi构成(i=1，2，.，n-1)。 根据定义，容易看出如果已经生成了 k-1 个元素的排列，那么，k 个元素的排列可以在 每个 k-1 个元素的排列 Pi前添加元素 i 而生成。 例如 2 个元素的排列是1,2和2,1，对于 3 个元素而言，p1是2,3和3,2，在每个排 列前加上 1 即生成1，2，3和1，3，2两个新排列，p2和 p3则是1，3，3，1和1，2， 2，1，按同样方法可生成新排列2，1，3，2，3，1和3，1，2，3，2，1。 程序代码如下： 厦门大学软件学院本科毕业论文 14 Private Sub Recu(P() As Integer, ByVal k As Integer) If k = n Then OutL P Else For i = k To n Swap P(k), P(i) Recu P, k + 1 Swap P(k), P(i) Next End If End Sub 3.6.33.6.3 循环移位法循环移位法 所谓循环移位是指如果已经生成了 k-1 个元素的排列，则在每个排列后添加元素 k 使之 成为 k 个元素的排列，然后将每个排列循环左移(右移)，每移动一次就产生一个新的排列。 例如 2 个元素的排列是1，2和2，1。在1，2，后加上 3 成为新排列1，2，3，将 它循环左移可再生成新排列2，3，1，3，1，2，同样2，1可生成新排列2，1，3， 1，3，2和3，2，1。 程序代码如下： Private Sub Cycl(P() As Integer,ByVal k As Integer) If k n Then OutL P Else For i = 0 To k - 1 t = P(1) For j = 2 To k P(j - 1) = P(j) Next P(k) = t Cycl(P,k + 1) Next End If End Sub 厦门大学软件学院本科毕业论文 15 厦门大学软件学院本科毕业论文 16 第四章第四章 TWDRI 算法介绍算法介绍 4.14.1 算法整体流程图算法整体流程图 算法整体有两部分组成：PurePermutation 和 MultisetPermutation,针对不同的输入调用不 同的函数，分别处理单集排列和多重集排列问题。 图 4-1 算法整体流程图 其中 N 表示输入字符串的长度，k 表示输入字符串中不重复字符的总个数。当 N=k 时， 表示该字符串是一个单集排列，可以调用 PurePermutation 函数，否则调用处理多重集合的 MultisetPermutation 函数。而且在处理多重集的时候，如果出现 N=k 的情况，程序会自动的 从 MultisetPermutation 函数转到 PurePermutation 函数。由于多重集的排列算法相对单集排列 算法会增加很多判断结构，因而运算时间也会比单集算法慢，所以此举可以换来程序效率的 极大提升。 厦门大学软件学院本科毕业论文 17 4.24.2 算法特色算法特色 算法中有引入一个自然数数组Mapping，它的作用主要是为了使算法具有通用性， 可以处理任意情况下的输入数据。当程序接受到一串数据后，可以通过 Mapping数组把它 们一一映射到自然数，即分别编号为 1，2，3，n，这样子，程序运行的时候可以直 接对这些自然数操作，而避免了因对字符或者其他复杂数据类型换位时的时间消耗。 例如：对于字符串“abbc”来说，经过预处理后，都有： N = 4; k =3; n0 =1, n1 =2, n2 = 1; Mappings0 =0, Mappings1 =1, Mappings2 =2; 而对于输入“#$”来说，经过预处理后，同样有： N = 4; k =3; n0 =1, n1 =2, n2 = 1; Mappings0 =0, Mappings1 =1, Mappings2 =2; 最后，Mapping会把每个排列结果再一一映射回原来的数据，以此实现对任意数据排列 的目标。 4.34.3 时间复杂度分析时间复杂度分析 算法的计算时间 T(n)满足： (4-1) 12 3 (1)(3) ( ) (3) nT nC nCn T n Cn 输入规模为 n3 的问题可由 n 个输入规模为 n-1 的子问题构成。C1n+C2是对子问题结 果进行分解和合并的花费，其中，为常数。当 n=3 求解问题的花费为，为常数。 1 C 2 C 3 C 3 C 厦门大学软件学院本科毕业论文 18 . . 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 图 4-2 的递归树 12 ( )(1)T nnT nC nC 从树的根结点开始，根有 n 个分支，第二层的每个节点有 n-1 个分支，一直到倒数第二层的 每个节点有 2 个分支，共 n+1 层。树的第一层有 1 个节点，第二层有 n 个节点，以下各层依次节 点数为 n(n-1)， n(n-1)(n-2) ，最后一层为 n！个。 接下来分析在每层的花销。新算法的最大特点在于随着递归层数的增加子问题的取值空间不 断缩小，因此在每个节点上对子问题的分割和合并的花费也从第一层的 C1n+C2到最后一层的 C1+C2不断下降。 本文的算法无需到达树结构的最后一层，而在倒数第三层时便能输出排列。因为在递归树中 一层节点的数目与其以上所有祖先节点的数目之和相近，所以最低两层的排除能带来性能的提高。 总的时间花费有： 厦门大学软件学院本科毕业论文 19 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 123 5171 ()() ! 266 C eC eCn 对于输入元素个数为 n 的全排列问题，其输出的规模为 n！。因此时间复杂度中的 n！ 是由问题本身固有的内在特点所决定的。本文算法的时间复杂度最终可以表示为 Cn！(C 为 常数)。 厦门大学软件学院本科毕业论文 20 第五章第五章 平均测试模型平均测试模型 5.15.1 整数拆分的理论基础整数拆分的理论基础 为了全面客观的比较各个算法的性能，我们需要对随机输入长度为 N 的字符串的所有 情况进行测试。一个输入的产生可以看成是从 N 个字符中每次抽取 1 个字符填满 N 个有序 格子。每个格子都有 N 种字符可选，所有共有 NN种输入情况。 然而我们不必测试所有的 NN种输入，因为其中有些输入的排列时间是相同的。以长度 4(N4)为例，显然输入“AAAA”和“BBBB”进行排列时间相同，输入“AABB” ， “CCDD”和“BCBC”的排列时间也是一样的。这样我们就可以对所有的输入情况进行分 类，把那些具有相同排列时间的输入划分到一类中。到时我们只需测试每类中的一个输入的 排列时间 t，再将时间 t 乘以该类的输入个数 cd就可以得到该类所有输入情况的排列时间 td。下面将介绍分类的过程： 分类的可以抽象为对正整数 N 的分拆。正整数 N 的一个分拆是 N 作为称作部分的一个 或多个正整数的无序和的一种表示。由于部分的顺序是不重要的57，因此我们总可以排列这 些部分使得它们的顺序从最大到最小。1，2，3，4 和 5 对应的分拆为： 表 5-1 整数分拆举例 数字对应分拆 11 2 2，11 3 3，21，111 4 4，31，2+2，211，1111 5 5，41，32，311，221，2111，11111 n 的一个分拆有时候写成 厦门大学软件学院本科毕业论文 21 (5-1） 21 2 1 n aaa n 其中 ai为非负整数，该数等于值为 i 的部分的个数(这个表达式是纯符号性的；它的项 既不是指数式，表达式也不是一个乘积)。当被写成公式(3)的形式时，若 ai0，则项通 i a i 常被省略，使用这个记号，4 的分拆为： 41，3111，22，2112，14 的每种形式对应一种分类。这 5 种分拆就对应长度为 4 的随机输入的 5 21 2 1 n aaa n 种分类： 表 5-2 长度为 4 的所有分拆情况 dOne instance 1 n i i a td 141AAAA1(A)t1 23111AAAB2(AB)t2 322DDCC2(DC)t3 42112AABC3(ABC)t4 514ABCD4(ABCD)t5 某类中如果有项，则该类有 ai个重复出现 i 次的字符。显然各项 ai的和 21 2 1 n aaa n i a i A(A=)就是构成一个输入字符串的不同字符的个数。 1 n i i a 5.25.2 平均时间测试模型平均时间测试模型 我们还需要计算每种分类包含的输入情况的个数。还是以长度 4 为例，不失一般性假设 组成输入字符串的字符集合为A，B，C，D。每种分类各项 ai的和 A 代表组成该类一个输 入情况的字符个数，而从字符集合中选取 A 个字符有种选法。表 5-2 第 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。所以要对每种选择的字符进行排列，有排列个数 厦门大学软件学院本科毕业论文 22 =3。AABC，BAAC 和 BACA 也是不同的，个数为= 1 !/ N i Aai 3!/(1! 2!)11 !/( !) a N i jk Ni =12。 4!/(2!1!1!) 每个分类中输入情况的个数为： (5-2) 111 (!/) (!/( !) d a NN i A dNd ijk cCAaNi i 至此我们可以得到平均时间的计算公式： (5-3) / N dd TctN 厦门大学软件学院本科毕业论文 23 第六章第六章 模拟和比较模拟和比较 6.16.1 测试环境与案例测试环境与案例 借鉴以往大型模拟比较经验56我们与之前 11 个比较著名的算法进行了比较。为保证公 平性，所有程序都用 C 语言实现（ANSI C 标准） ，均在配置为 Pentium 4 CPU 2.93 GHz 和 1 GB 内存的电脑上运行。所有算法都在相同的环境下运用第五章中的平均测试模型进行 公平、全面的比较。 我们的测试案例是从数字 0-9 和字母 a-z 中选取。 例如：如果 N =5，我们使用“01234” ；如果 N =17，我们使用“0123456789abcdefg” 。 6.26.2 时间与内存比较时间与内存比较 图例说明：图例说明： Heap63: 递归交换算法1 Heap63: 迭代交换算法1 Ives 76: 迭代交换算法2 JT: 算法3bLoopless Johnson-Trotter3 JTLLC03: Jeeve Technologies LLC算法7 KL97: Korsh和Lipschutz常数时间算法4 KL04: Korsh和LaFollette基于数组的loopless算法9 Ruskey 03: Ruskey算法53 Sedgewick02: Sedgewick算法6 Takaoka99: Takaoka 的O(1)算法5 TV06: Takaoka和Violich的算法10 厦门大学软件学院本科毕业论文 24 表 6-1 和图 6-1 说明 TWDRI 算法至少是其它 5 种算法中任何一个速度的 3 倍。 表 6-1 多重集全排列算法的平均时间 (单位：毫秒) 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,564 0.00E+00 5.00E+05 1.00E+06 1.50E+06 2.00E+06 2.50E+06 3.00E+06 3.50E+06 4.00E+06 4.50E+06 5.00E+06 5.50E+06 1112131415 (N) (Time/ms) TWDRIKL97KL04Ruskey 03Takaoka 99TV06 图 6-1 多重集全排列算法的平均时间比较 表 6-2 说明 TWDRI 算法内存花销相对其它算法较少。 表 6-2 多重集全排列算法的峰值/平均内存比较 (单位: KB) NTWDRI KL97KL04Ruskey03Takaoka 99 TV06 11768768813813780780728728788788864864 12772772832832788788732732792792868868 13776776859859792792736736800800876876 厦门大学软件学院本科毕业论文 25 14772772897897796796740740812812888888 15784784941941804804748748824824896896 16800800752752 在输入为单集的情况下，TWDRI 算法的速度是其它 5 种多重集算法中最快算法的 9 倍。 表表 6-36-3 输入无重复的多重集全排列算法时间比较输入无重复的多重集全排列算法时间比较 ( (单位：毫秒单位：毫秒) ) NTWDRIKL97KL04Ruskey 03Takaoka 99 TV06 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 17713,381,937 0.00E+00 2.00E+08 4.00E+08 6.00E+08 8.00E+08 1.00E+09 1.20E+09 1.40E+09 10111213141516 (N) (Time/ms) TWDRIKL97KL04Ruskey 03Takaoka 99TV06 图图 6-26-2 输入无重复的多重集全排列算法时间比较输入无重复的多重集全排列算法时间比较 厦门大学软件学院本科毕业论文 26 从表 6-4 和图 6-3 中可以看出，Ives 76 是其它 6 种算法中最快的；而 TWDRI 算法的速 度是 Ives 76 算法的 1.3 倍。 表 6-4 输