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

1、 本科毕业论文 (科研训练、毕业设计 ) 题 目： 多重集全排列 算法 研究 - Alternative 算法 概述 及测试 比较 姓 名： 学 院：软件学院 系： 专 业： 软件工程 年 级： 学 号： 指导教师： 陈金柱 职称： 年 月I 摘 要 全排列算法问题的研究已经有很悠久的一段历史。在简单回顾 和评价了 历史上 经典 的排列算法 之后 ， 提出了 一种新的全排列产生算法 TWDRI。该算法能同时解决无重复输入的单集问题和重复输入的多重集 问题 。 不同于大多数排列产生算法只能处理数值的特性，本算法 适用于各种不同字符的输入情况，具有通用性。 为了能客观评价现有各种排列算法的性能，

2、选取经典全排列算法进行分析和比较，并且 进行了大量的模拟，测试了从 10 位到 17 位的输入情况，与 世界上 已知最快 的 和最近的算法进行比较 。通过数据分析表明， TWDRI 算法 速度是世界上已知最快多重集排列 算法 的 2 倍 。 关键词 多重集 排列 算 法 TWDRI II Abstract The researching of the permutation algorithm already had glorious phase of histories. After looks back into and has appraised in simply the histor

3、y 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 val

4、ue 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

5、, 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

6、2 times. Key words multiset； permutation； algorithm； TWDRI III 目 录 第一章 引言 . 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 算法

7、. 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 IV 5.4.4 TWDRI 算法与其它多重集排列算法的速度

8、比 . 26 结论 . 29 致谢语 . 30 参考文献 . 31 V Contents Chapter1 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 Ivess Iterative Algorithm

9、. 7 3.3 Multiset Permutation Algorithm Based on Grad-Code Order . 9 3.4 Heaps 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 Chapter5

10、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 Permutatio

11、n. 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 VI 5.4.4 Speed Rations of TWDRI Algorithm to Others . 26 Conclusion . 29 Acknowledgement . 30 References . 31 多重集全排列算法研究 1 第一章 引言 所谓全排列，即 对给定的 N 个字 符进行排列组

12、合，得到 N！ 种准确 无重复无遗漏 的排列结果。 全排列问题 不仅仅 是一个 组合 数学问题， 而且在计算机领域通过不同方法对各种全排列算法之间进行比较 有着 特殊的意义 。 全排列问题有着悠久的历史， 排列 的产生可以追溯到十六世纪五十年代 ，早在 1960 年 D.H.Lehmer 就 发表了关于这 一领域算法的总结性文章 1。计算机的出现使更多的人投入对 N！ 问题的研究，普林斯顿大学的 Robert Sedgewick 教授在1977 年发表在 ACM Computing Surveys 上的论文 2提到在短短二十年间发表的关于 N 个元素的 N！ 全排列的算法就超过 30 多种。

13、生活中也有很多实际问题与全排列问题密切相关。 全排列问题也有着广泛的实际应用，比如说在密码学领域对输入的一些数字或字符产生其对应的密码；在生物医学领域 DNA 的全排列等等。因此研究字符串的全排列问题有很大的实际意义。 对于 N 个数来说，其全排列的个数有 N!个 ,近五十年来出现了许多关于全排列的算法 ,它们的思想各不相同 ,因此执行效率和所用的时间也各不相同。 本文第 三 章回顾和评价了历史上经典的排列算法，随后在第 四 章介绍了新排列算法TWDRI 的基本模型，第 五 章给出了 TWDRI 算法与已知的最 快或者最新的算法比较的方法与结果。 最后，得出结论： TWDRI 算法是目前世界上

14、处理 多重集 全排列问题最快的算法。 多重集全排列算法研究 2 第二章 研究背景 2.1 单重集 全排列 定义 定义 1： 给定的字符串不包含重复字母，将其进行全排列，把其 所有可能的全排列 准确无重复无遗漏地 列 举出来。 例如：输入 ABC，其全排列的结果有 6 种 ,分别为：ABC,ACB,BAC,BCA,CAB,CBA。 2.2 多重集 全 排列 定义 定义 2：我们把 N 个字符长度的字符串 S 看成一个多重集，字符串 S 包含 k 个不同的字符，每个字符的个数分别为 n0, n1, , nk-1。 显然， N = n0 + n1 + nk-1。 显然 当 N=k 时，我们把此时的多

15、重集称为单重集，因为此时 n0 = n1 = nk-1 = 1，每个不同字符的个数有且仅有一个。即我们一般意义上的无重复输入。 定义 3：对于长度为 N，有 k 个不同字符，每个字符个数分别为 n0, n1, , nk-1 的多重集，我们把 n0, n1, , nk-1 称为每个字符的重复个数。 定理 1： 令 S 是长度为 N 的多重集，它有 k 个不同的元素，每个元素的重复数分别为 n0, n1, , nk-1，那么，多重 集 S 的排列数 =0 1 1! !. !kNn n n，其中 N = n0 + n1 + nk-1。 证明： 将 n个元素的集合划分成 k 个被做标签的盒子 B1,B

16、2, ,Bk， 其中盒 1 含有 n1 个元素，盒 2 含有 n2 个元素，盒 k 含有 nk 个元素。首先选取 n1 个元素放入第一个盒子，然后从剩下 n n1 的个元素中取 n2 个元素放入第二个盒子，然后从剩下的 n n1 n2 个元素中取n3 个元素放入第三个盒子， 依此类推，最后将 n n1 nk-1 nk 个元素放入第 k 个盒子。由乘法原理，进行选择的总方法数为 ，即 。 多重集排列是个数学模型，对于每一个输入字符串，多重集排列应该 无重复无遗漏 地列举出所有的可能排列组合。通常，我们随机输入一个长度为 N 的字符串，希望多重集排列 算法能准确快速的产生所有可能的排列。 例如，当

17、我们输入的字符串为“ 0112”时，我们可以得到： 多重集全排列算法研究 3 N = 4, k =3, n0 =1, n1 =2, n2 = 1； 其所有产生的排列数为 4!1!2!1!=12，分别为： 0211， 0112，0121， 1210， 1201， 1021， 1120， 1102， 1012， 2011， 2110， 2101。 2.3 多重集排列的研究历史 大部分科学家，特别是计算机和数学领域的专家，当他们需要列举所有可能性并核对所希望结果的时候，经常会碰到这 样或那样的问题，事实上，这些问题都属于全排列问题。单重集排列和多重集排列在很多领域都有广泛的应用，例如 DNA 排序，

18、密码学，运筹学，电路设计，统计学和化学领域等等。 科学教对单重集排列和多重集 排列算法有着三百多年的研究历史， 排列 产生的历史可以追溯到 十六世纪五十年代 。 关于 单重集 排列问题，已知最早的算法 1605 年 在 英国 教堂产生的，当时，教堂中的牧师用它来计算几口大钟不同的撞击顺序，以此产生各种不同的音乐效果。普林斯顿大学计算机系 Robert Sedgewick 教授 在 1977 年对众多排列产生方法中的经典算法做了分析 和比较 2。在众多算法中具有代表性的有 M. B. Wells在 1961 年发表的 递归算法 3， 1965年 J. Boothroyd 对其进行了改进 4； 1

19、962 年 S. M. Johnson5和 H. F. Trotter6分别独立提出的 邻位交换法 是具有 重大突破 意义 ； 阶乘计算 算法是 Johnson-Trotter 算法的另一种实现； 同样是在 Johnson-Trotter 算法的基础上 G. Ehrlich78引进了减少内部循环的思想得到 “ Loopless”算法，这一算法被 N. Dershowitz 进 一步的优化；其它还有 F. M. Ives 的 递归算法 9； C. Tompkins 和 L. J. Paige 的 嵌套循环算法 10 , Peck 和 Schrack 给出了这一算法的 ALGOL 程序11，还有许

20、多研究人员对这一算法进行改进 14172432363739；比较有影响的算法还有 字典序算法 11161923263031， 随机排列算法 1113242528和 选择排列算法 1516。 与 单重集 排列相比，多重集排列算法的发展起步较晚 。 多重集输入是一个相对较难的问题，不少研究者一直在寻求一个高性能的算法。多重集的排列一般是按字典序给出。另一种常见的排列顺序是 格雷码顺序 ， 即每相邻两个排列之间 只有一个数位发生变化 。 James F. Korsh 和 Paul S. Lipschutz 在 Johnson 算法的基础上结合 Lehmer 的思想得到第一个使用少循环的多重集排列产生算法 17。 在这个新算法中，多重集的排列是以链表形式产生的，链表中的操作都是由指针来完成， 其中 包括 O(1)时间的 交换操作 。两年后， Takaoka 使用数组改进了这个O(1)时间的 算法 5。 在求解多重集排列问题时传统算法为防止重复输出而保存大量纪录信息，许多研究人员投入精力简化信息的保存和判断验证过程，也产生了许多精妙的算法。但这些