多重集全排列算法研究Alternative算法概述及测试比较

本科毕业论文 （科研训练、毕业设计） 目：多重集全排列算法研究 一 Alternative算法概述及测试比较 姓 名： 学 院：软件学院 系： 专 业：软件工程 年 级： 学 号： 指导教师：陈金柱 职称: 全排列算法问题的研究已经有很悠久的一段历史。在简单回顾和评价了历史上经典的排 列算法之后，提出了一种新的全排列产生算法TWDRI。该算法能同时解决无重复输入的单集 问题和重复输入的多重集问题。不同于大多数排列产生算法只能处理数值的特性，本算法适 用于各种不同字符的输入情况，具有通用性。为了能客观评价现有各种排列算法的性能，选 取经典全排列算法进行分析和比较，并且进行了大量的模拟，测试了从10位到17位的输入 情况，与世界上已知最快的和最近的算法进行比较。通过数据分析表明，TWDRI算法速度是 世界上已知最快多重集排列算法的2倍。 ［关键词］多重集排列算法TWDRI Abstract The researching of the permutation algorithm already had glorious phase of histories. After looks back into and has appraised in simply the history the classical permutation algorithm, proposed one kind of new permutation algorithm TWDRI. This algorithm can simultaneously solve new permutation technique for multiset permutations and pure permutation. Is different has the algorithm in the majority permutation only to be able to process the value the characteristic, this algorithm is suitable for each kind of different character input situation, has the versatility. For can the objective evaluation existing each kind of permutation algorithm performance, the selection classics permutation algorithm carry on the analysis and the comparison, and has carried on the massive simulations, has tested from 10 to 17 input situations, known quickest and the recent algorithm carries on the comparison with the world. Indicated through the data analysis that the TWDRI algorithm speed is in the world known quickest multiset permutation algorithm 2 times. [Key words] multiset； permutation； algorithm； TWDRI 第一章引言 1 第二章研究背景 2 2.1单重集全排列定义 2 2. 2多重集全排列定义 2 2. 3多重集排列的研究历史 3 第三章历史上主要的排列算法 5 3. 1 Johnson and Trotter 算法 5 3. 2 Ives迭代算法 7 3. 3基于格雷码顺序的多重集排列算法 9 3. 4 Heap递归算法 10 3. 5 Alternative 算法 11 3. 6 Constant Time 算法 13 第四章TWDRI算法 15 4.1主要流程图 15 4. 2算法时间复杂度 15 4. 3 TWDRI算法的优点 17 第五章分析与比较 19 5. 1基于随机输入的平均时间计算模型 19 5. 2计算模型的推导过程 19 5. 3平均时间计算公式 21 5.4比较结果 22 5. 4. 1多重集算法的时间和内存开销比较 23 5. 4.2多重集算法在非重复输入的情况下的时间和内存占用比较 24 5.4. 3 TWDRI算法和其它单重集排列算法的时间和内存比较 25 5.4.4 TWDRI算法与其它多重集排列算法的速度比 26 结论 29 致谢语 30 ［参考文献］ 31 Contents Chapter 1 Introduction 1 Chapter2 Background 2 2.1 The Definition of Pure 2 2.2 The Definition of Multiset 2 2.3 The Study History of Multiset 3 Chapter3 Classical Algorithm 5 3.1 Johnson and Trotter Algorithm 5 3.2 Ives's Iterative Algorithm 7 3.3 Multiset Permutation Algorithm Based on Grad-Code Order 9 3.4 Heap，s Recursive Algorithm 10 3.5 Alternative Algorithm 11 3.6 Constant Time Algorithm 13 Chapter4 The TWDRI Algorithm 15 4.1 Main Flowchart 15 4.2 Time Complexity 15 4.3 Advantage of The TWDRI Algorithm 17 Chapters Simulation and Comparison 19 5.1 Computing Model Based on Random Input 19 5.2 Derivation of Computing Model 19 5.3 Computing Model for the Average Time of Mutliset Permutation 21 5.4 The Result of Simulation and Comparison 22 5.4.1 Comparison of Average Time and Memory of Mutliset Permutation 23 5.4.2 Comparison of Average Time and Memory with Distinct Elements 24 5.4.3 Comparison of Average Time and Memory of Pure Permutation 25 5.4.4 Speed Rations of TWDRI Algorithm to Others 26 Conclusion 29 Acknowledgement 30 References 31 第一章引言 所谓全排列，即对给定的N个字符进行排列组合，得到N!种准确无重复无遗漏的排列 结果。全排列问题不仅仅是一个组合数学问题，而且在计算机领域通过不同方法对各种全排 列算法之间进行比较有着特殊的意义。全排列问题有着悠久的历史，排列的产生可以追溯到 十六世纪五十年代，早在1960年D.H.Lehmer就发表了关于这一领域算法的总结性文章 计算机的出现使更多的人投入对N!问题的研究，普林斯顿大学的Robert Sedgewick教授在 1977年发表在ACM Computing Surveys上的论文’提到在短短二十年间发表的关于N个元素 的N!全排列的算法就超过30多种。 生活中也有很多实际问题与全排列问题密切相关。全排列问题也有着广泛的实际应用， 比如说在密码学领域对输入的一些数字或字符产生其对应的密码；在生物医学领域DNA的 全排列等等。因此研究字符串的全排列问题有很大的实际意义。对于N个数来说，其全排列 的个数有N!个，近五十年来出现了许多关于全排列的算法,它们的思想各不相同，因此执行效 率和所用的时间也各不相同。 本文第三章回顾和评价了历史上经典的排列算法，随后在第四章介绍了新排列算法 TWDRI的基本模型，第五章给出了 TWDRI算法与已知的最快或者最新的算法比较的方法与 结果。最后，得出结论：TWDRI算法是目前世界上处理多重集全排列问题最快的算法。 第二章研究背景 2. 1单重集全排列定义 定义1：给定的字符串不包含重复字母，将其进行全排列，把其所有可能的全排列准确 无重复无遗漏地列举出来。例如：输入ABC,其全排列的结果有6种，分别为： ABC, ACB, BAC, BCA, CAB, CBA。 2. 2多重集全排列定义 定义2：我们把N个字符长度的字符串S看成一个多重集，字符串S包含k个不同的字 符，每个字符的个数分别为n（）, ni,…,nk_io显然，N = n0 + ni +•••+nk_io显然当N=k时，我 们把此时的多重集称为单重集，因为此时no = ni="・=nki = l,每个不同字符的个数有且仅有 一个。即我们一般意义上的无重复输入。 定义3：对于长度为N,有k个不同字符，每个字符个数分别为no, ni,…，nki的多重 集，我们把no,叽…，队一 1称为每个字符的重复个数。 定理1：令S是长度为N的多重集，它有k个不同的元素，每个元素的重复数分别为no, nb…，如一1，那么，多重集S的排列数= ,其中N = n（）+ ni+・"+nk-i。 ?70!"] !...7妇！ 证明：将n个元素的集合划分成k个被做标签的盒子Bi, B2,…,Bk,其中盒1含有山个元 素，盒2含有8个元素，…，盒k含有队个元素。首先选取鱼个元素放入第一个盒子，然 后从剩下n-m的个元素中取8个元素放入第二个盒子，然后从剩下的n-m-n2个元素中取 113个元素放入第三个盒子，依此类推，最后将n—ni nk.i = nk个元素放入第k个盒子。 由乘法原理，进行选择的总方法数为\ L即 应f 。 多重集排列是个数学模型，对于每一个输入字符串，多重集排列应该无重复无遗漏地列 举出所有的可能排列组合。通常，我们随机输入一个长度为N的字符串，希望多重集排列算 法能准确快速的产生所有可能的排列。 例如，当我们输入的字符串为“0112”时，我们可以得到： 4! N= 4, k =3, n0 = l, m =2, n2= 1；其所有产生的排列数为一 =12,分别为：0211, 0112, 1!2!1! 0121, 1210, 1201, 1021, 1120, 1102, 1012, 2011, 2110, 2101。 2. 3多重集排列的研究历史 大部分科学家，特别是计算机和数学领域的专家，当他们需要列举所有可能性并核对所 希望结果的时候，经常会碰到这样或那样的问题，事实上，这些问题都属于全排列问题。单 重集排列和多重集排列在很多领域都有广泛的应用，例如DNA排序，密码学，运筹学，电 路设计，统计学和化学领域等等。 科学教对单重集排列和多重集排列算法有着三百多年的研究历史，排列产生的历史可以 追溯到十六世纪五十年代。关于单重集排列问题，已知最早的算法1605年在英国教堂产生的， 当时，教堂中的牧师用它来计算几口大钟不同的