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

1、厦门大学本科毕业论文 I 本科毕业论文 (科研训练、毕业设计 ) 题 目：多重集全排列算法研究 姓 名： 学 院：软件学院 系：软件工程系 专 业：软件工程 年 级： 学 号： 指导教师 （校内） ： 职称： 年 月厦门大学本科毕业论文 I 多重集全排列算法研究 摘要 全排列算法 按处理输入的能力可 分为 集合 (set)排列算法和多重集 (multiset)排列算法。多重集中 一个元素可 多次出现 ，多重集排列算法不会产生重复的排列 。 本文介绍 了 一种新的全排列产生算法。该算法能同时解决 集合 排列 问题和多重集 排列 问题；适用于各种不同字符的 输入情况，具有通用性。与已有算法不同，新

2、算法 不采用交换 产生排列 而是 先 计算 输入 中不同 元素 (distinct element)的 出现 次数 (multiplicity)，再将各个不同输入字符一对一映射到连续的自然数 集合 。排列过程中仅对自然数 数 组进行操作， 递归求解时 能 不断缩小子 问题的取值空间，实现无需进行大量判断自动排除重复输出。最后排列 结果根据自然数 到 字符 的逆映射得到。 文章 选取经典 全排列 算法进行分析 和比较 。 我们进行了大量的模拟，测试了从 10 位到17 位的输入情况，与已知 最新 和 最快 的算法进行比较 12345678910， 新 算法 速度 是世界上已知最快 多重集排列 算

3、法 的 3 倍 ，同时也比已知最快集合排列算 法 快 30%。 关键词 多重集 全 排列 算法 厦门大学本科毕业论文 II A Research into Multiset Permutation Algorithm Abstract Permutation algorithms can be divided into two groups: set permutation algorithms and multiset permutation algorithms. Multiset differs from a set in that each member has a multiplic

4、ity. Multiset has repeated elements, such as a,a,b,b,b,c. We consider any character string of length N as a multiset, which has k different characters, each has count n1, n2, , nk, respectively. Clearly, N = n1 + n2 + n k. For the input string, the multiset permutation generates all possible permuta

5、tions without redundancy. When N=k, it is a pure permutation since n1 = n2 = n k = 1. Numerous algorithms were proposed in publication since the research history of this problem is quite long. Unfortunately, multiset permutation is tougher problem with fewer outcomes. A new permutation algorithm is

6、described. This algorithm can be applied in set and multiset. In both case, it has a high performance. The new algorithm first calculates the frequency of each distinct element in the input, and then maps the distinct elements to natural numbers. In the process of permutation, it only deals with nat

7、ural numbers. The TWDRI algorithm eliminates unnecessary switches and reduces the loop times in order to speed up the permutation and to reduce memory consumption. We also compare the new algorithm with several other algorithms. This paper analyses several classical algorithms in this field. We eval

8、uate 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 NN inputs with each fixed length N above. We compare our results with the eleven (11) fastest know

9、n and/or well-known algorithms12345678910 in detail. The comparisons show 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. Key words Multiset Permutation Algorithm 厦门大学本科毕业论文 III 目录 第一章 引言 .1 第

10、二章 典型全排列算法分析 .3 2.1 Johnson and Trotter 算法 .3 2.2 Takaoka 算法 .6 2.3 Ives 算法 .8 2.4 字典序法 .9 第三章 TWDRI 算法 . 12 第四章 平均 时间 测试模型 . 15 第五章 模拟和比较 . 17 5.1 模拟 环境 和 比较 方法 . 17 5.2 多重集算法的时间和内存花销比较 . 17 5.3 多重集算法在集合输入下的时间和内存花销比较 . 18 5.4 TWDRI 算法和其它集合排列算法的时间和内存比较 . 19 5.5 TWDRI 算法与其它多重集排列算法的比较趋势分析 . 21 第六章 应用与

11、总结 . 22 致谢语 . 23 参考文献 . 24 厦门大学本科毕业论文 IV Contents Chapter 1 Introduction . 1 Chapter 2 Classic Algorithms Analysis. 3 2.1 Johnson and Trotter Algorithm . 3 2.2 Takaoka Algorithm . 6 2.3 Ives Algorithm . 7 2.4 Lexicographic Algorithm . 9 Chatper 3 TWDRI Algorithm.12 Chapter 4 Average Calculation Mode

12、l .15 Chapter 5 Simulation and Comparison .16 5.1 Simulation Environment and Comparison Method .16 5.2 Average Time and Memory Consumption of Multiset Permutation .16 5.3 Time Comparison of Multiset Permutation for Inputs with Distinct Elements.17 5.4 Time and Memory Consumption of Pure Permutation

13、Algorithm and TWDRI .18 5.5 Speed Ratios of TWDRI Algorithm to Other Multiset Permutation Algorithms.21 Chapter 6 Application and Conclusion .22 Acknowledgments .23 References .24 厦门大学本科毕业论文 1 第一章 引言 四个碱基 手拉手创造了怒放的生命 ；七只音符的交织谱出美妙的乐章。 我们身边很多美丽的事物都是由简单的元素 组合 排列而成 ， 整个世界也可以看成 是几种 基本粒子 排列组合 的杰作 。 科学家 一直

14、在带领着我们认识这个 神奇 的世界 ， 探寻她美丽背后的奥秘。 而我们在深入认识事物时总是努力分析其基本构成要素，然后再研究这些要素 是如何联系起来构成 多种多样不同的整体 。 尤其是计算机科学家和数学家 ， 在研究中需要列出所有的可能 情况 以获取一种渴望的特征时， 列出 排列组合 是不可或缺的一步 。 DNA 分析 、加密解密、电路设计、运筹研究、统计计算、化学 ，这些领域 中 你都可以看到排列与组合 的 应用 。 排列 产生的历史可以追溯到 十六世纪五十年代 ， 教堂中的牧师计算几口大钟不同的撞击顺序 来产生各式的音乐效果 。 集合和多重集全排列算法有着三百多年的研究历史12345678

15、91011121314151617181920212223242526272829303132333 4353637383940414243444546474849505152535455。 早在 1960 年就有这一领域算法的总结性文章出现13。 图灵奖获得者 Donald E. Knuth 在其经典著作计算机程序设计艺术一书中写道 50：“事实上，排列 (permutations)问题在计算机领域 非常 重要。 Vaughan Pratt 提议直接把它 叫做 perms。如果 Pratt 的建议得以实施，那么计算机 教科书的厚度将变得薄一些 (相应书的价格也会便宜一点 )”。虽然 Knut

16、h 语带幽默，但由此可见排列 在计算机领域出现的频率之高。正是因为排列问题如此重要，所以一直以来有众多的研究人员致力于该问题的解决。 普林斯顿大学计算机系 Robert Sedgewick 在 1977 年对众多排列产生方法中的经典算法做了分析和比较 3。在众多算法中 具有代表性的有 M. B. Wells 在 1961 年发表的 Recursive method15， 1965 年 J. Boothroyd 对其进行了改进 2628； 1962 年 S. M. Johnson21和 H. F. Trotter20分别独立提出的Adjacent exchanges 是一重大突破 ； Facto

17、rial counting 算法是 Johnson-Trotter 算法的另一种实现 ； 同样是在 Johnson-Trotter 算法的基础上 G. Ehrlich3334引进了减少内部循环的思想得到 “Loopless”算法，这一算法被 N. Dershowitz 进一步的优化 ； 其它还有 F. M. Ives 的 iterative method2； C. Tompkins 和 L. J. Paige 的 Nested cycling 12, Peck 和 Schrack 给出了这一算法的ALGOL 程序 17，还有许多研究人员对这一算法进行改进 13142432363739； 比较有

18、影响的算法还有 Lexicographic algorithms1116181922252930与 Random permutations1323242731。以厦门大学本科毕业论文 2 上这些算法仅能解决无重复输入的 集合排列 问题。 多重集输入是一个相对较难的问题，不少研究者一直在寻求一个高性能的算法 45384054。 多重集的排列一般是按字典序给出 。另一种常见的排列顺序是 Gray code，在 Gray code 的排列中相邻的两个排列中仅有两个元素的位置不同。 James F. Korsh 和 Paul S. Lipschutz 在 Johnson 算法的基础上结合 Lehmer

19、 的思想得到第一个使用少循环的多重集排列产生算法 4。 在求解多重集排列问题时传统算法为防止重复输出而保存大量纪录信息，许多研究人员投入 精力 简化信息的保存和判断验证过程，也产生了许多精妙的算法。但这些算法都始终没有突破通过保存和判断信息来防止重复输出的思维藩篱。 排列问题的一大 特点就是输出 规模受输入规模的影响极大。 我们假设计算机进行一次运算就能给出一个排列 (实际的算法不可能做到这点 )。 如 表 1-1 所示 ， 对于一台运算速度为百万次每秒的计算机， 给出 11 个元素的集合的所有 11！ = 399168 个排列只需几秒钟的时间，而要得到 17 个元素 的所有 17！ = 35

20、5687428096000 个排列 则 需要几年。 就算是当前最快的计算机，其运算速度达到万亿次每秒，要计算出大于 20 个元素的集合的所有排列在时间上也显得不太可能。 在科学研究中确实可能遇到较大规模的排列需求，除了配置高性能的计算机外 ，找到一个高性能的排列算 法就显得非常重要 。 表 1-1 不同性能计算机在各种输入规模下进行排列所需 时间 N 排列的个数 百万 /秒 十亿 /秒 万亿 /秒 10 3628800 11 39916800 几秒 12 479001600 几分钟 13 6227020800 几小时 几秒 14 87178291200 天 分钟 15 130767436800

21、0 几周 几分钟 16 20922789888000 几个月 几小时 几秒 17 355687428096000 几年 几天 几分钟 18 6402373705728000 几个月 几小时 19 121645100408832000 几年 几天 20 2432902008176640000 月 微不足道 的时间 漫长的等待 厦门大学本科毕业论文 3 第二章 典 型 全 排列 算法 分析 这章我们介绍几种典型 的 全 排列算法，它们不仅 性能高效而且 其算法思想也很有启示意义。 在详细介绍各种排列算法之前有必要 明确 集合排列 问题 与多重集排 列 问题 的不同。 集合排列算法只能解决输入是集合

22、的问题，这就要求输入中的每个元素与输入中的其它元素不同，元素间是互异的。 我们知道多重集的 N 个元素中可以有相同的元素，不同 元素的个数为 k，每个元素的重复次数为 n1， n2,n k，显然 N = n1 + n2 + + n k。当 N = k 时， n1 = n2 = = n k = 1，多重集退化为集合。 因此多重集排列算法也可以解决集合排列问题。 对于集合 1， 2， 3集合排列算法给出全部 6 个排列： （ 1） 213 （ 2） 231 （ 3） 321 （ 4） 312 （ 5） 132 （ 6） 123 以多重集 1， 2， 2为例，集合排列算法给出该多重集的排列为： （

23、1） 212 （ 2） 221 （ 3） 221 （ 4） 212 （ 5） 122 （ 6） 122 其 中 (1)和 (4)是一样的， (2)和 (3)、 (5)和 (6)也是相同的。 而我们一般并不希望得到的排列结果中有重复的情况，因此多重集排列算法更具一般性。但也正是因为多重集排列算法需要排除重复的输出，所以多重集排列算法很难达到像集合排列算法一样的性能。 2.1 Johnson and Trotter 算法 1962 年 S. M. Johnson21和 H. F. Trotter20分别独立提出的相邻换位方 法是 集合排列算法一个重大的突破。以后的很多算法都是在他们算法上的改进 3

24、33435。他们发现通过 N!-1 次相邻元素的交换可以产生 N 个元素的所有 N！ 个排列。其实算法的思想来源很自然，如果我们已经知道 N-1 个元素的所有 (N-1)!个 排列； 每次 将新的第 N 个元素插到原 来每个 排列中所有可能的 N 个空隙中 便可以得到 所需的 N！ 个排列。 图 2-1 是 5 个元素 排列产生 过程 中 最开始 的 4 次交换。已知四个元素 BCDE 的排列，首先把新的第五个元素 A 插到 BCDE 的前面得到 ABCDE，然后通过 A 与其后元素的四次交换就得到 5 种所有可插入位置的排列。 从 B, C, D, E的 1 个排列得到了 A, B, C,

25、D, E的 5 个排厦门大学本科毕业论文 4 列。 ABCDEBACDEBCADEBCDAEBCDEA图 2-1 A 插入排列 BCDE 过程 Algrithm 1 (Johnson and Trotter) 1 i 1 2 for i 1 to N 3 do i i + 1 4 ci 1 5 di true 6 c1 0 7 for i 8 while i 1 9 do i N 10 x 0 11 while ci = i 12 do if di = false 13 then x x + 1 14 if di = true 15 then di false 16 if di = true

26、17 then k ci + x 18 else k j ci + x 19 do swap pk pk+1 20 ci ci + 1 21 OuputPerm 厦门大学本科毕业论文 5 上一步我们从 B, C, D, E的 1 个排列得到了 A, B, C, D, E的 5 个排列。为了产生过程继续进行 ， 首先需要得到 B, C, D, E的另一个排列，同样我们把 B 看成是新元素插入到 CDE的排列中得到 CBDE。现在就可以把 A 插到 CBDE 的空隙中得到另外 5 个排列了。 图 2-2 表现的就是上面的过程。 ABDEBCDEACBDAECBADECABDEACBDECBDEA图

27、 2 -2 BCDE 换为 CBDE 后 A 向反方向移动 从图 2-3 可以看出 N 个元素的排列网络中被框起来的部分构成了 N-1 个元素的排列网络。也可以看成是在 N-1 个元素的排列网络中插入第 N 个元素从左到右的移动或是从右到左的移动便得到 N 个元素的交换 网络。 A BB AA B CB A CB C AC B AC A BA C BA B C DB A C DB C A DB C D AC B D AC B A DC A B DA C B DA C D BC A D BC D A BC D B AD C B AD C A BD A C BA D C BA D B CD A B CD B A CD B C AB D C AB D A CB A D C A B D CN = 3N = 2N = 4