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

1、 I 多重集全排列算法研究 摘要 本文提出一种新的全排列产生算法 TWDRI。该算法能同时解决一般的无重复输入 的单集 (pure permutation)问题和输入有重复的多重集 (multiset permutation)问题 ， 而且适用于各种不同字符输入情况 ， 具有通用性。与已有算法不同，本文的新算法首先根据输入字符的频率预排序，再将各个不同输入字符一对一映射到连续的自然数数组。排列过程中仅对 该 数组进行操作，在适当的时机对数组元素换位，从而不断缩小子问题的取值空间，无需进行大量判断 就可以 自动排除重复输出。最后 排列的结果 再 根据自然数与字符对应关系得到。而且对于多重集，本文

2、提出了一种新的评估 多重集 算法性能的方法 平均时间 (average time of multiset permutations)，对于长度为 N 的输入，由它产生的所有的 NN种情况都进行测试。 我们进行了大量的模拟，测试了从 10 位到 17 位的输入情况，与已知的算法进行 了 比较12345678910，本文提出的算法表现出优秀的性能，比已有算法使用更 快 的时间得到所有排列结果。 关键词 全 排列 多重集 算法 II A Research into Multiset Permutation Algorithm Abstract We introduce a new permutati

3、on generation method TWDRI. 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

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

5、alue-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 alg

6、orithms, 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 ou

7、r 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 第二章 多重集排列的相关定义 . 3 2.1 多重集排列的理论基础 . 3 2.2 关于多重集排

8、列的定理 . 3 第三章 经典字符排列算法分析 . 5 3.1 字典序法 . 5 3.2 递增进位制数法 . 6 3.3 递减进位制数法 . 8 3.4 邻位对换法 (格雷码序法 ) . 10 3.5 元素增值法 (N进制法 ) . 11 3.6 递归类算法 . 12 第四章 TWDRI 算法介绍 . 15 4.1 算法整体流程图 . 15 4.2 算法特色 . 16 4.3 时间复杂度分析 . 16 第五章 平均测试模型 . 19 5.1 整数拆分的理论基础 . 19 5.2 平均时间测试模型 . 20 第六章 模拟和比较 . 22 6.1 测试环境与案例 . 22 6.2 时间与内存比较

9、. 22 第七章 应用与总结 . 27 致谢 . 28 参考文献 . 29 IV Contents Chapter 1 Introduction. 1 Chapter 2 The Definition of Multiset Permutation. 3 2.1 The Basic Theoretics of Multiset Permutation . 3 2.2 The Theorems of Multiset Permutation. 3 Chapter 3 Classic Algorithms Analysis . 5 3.1 Lexicographic Order. 5 3.2 In

10、crease by Degrees Carry. 6 3.3 Decrease by Degrees Carry. 8 3.4 Adjacent Exchange(Grad Code) .10 3.5 Element Increment. 11 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 . 1

11、9 5.1 The Basic Theoretics of Integer Split.19 5.2 Average Time Calculation Model.20 Chapter 6 Simulation Environment and Comparison. 22 6.1 Simulation Environment and Cases .22 6.2 Comparison of Time and Memory .22 Chapter 7 Application and Summary . 27 Acknowledgments . 28 References . 29 厦门大学软件学院

12、本科毕业论文 1 第一章 引言 在论文最开始， 我们 有必要 明确单集 排列 问题 与多重集排列 问题 的不同。 我们把无重复输入排列称为 “单集”排列或者 Pure Permutation； 把无重复输入的集合称为“单集”。 而有重复输入排列称为“多重集”排列或者 Multiset Permutation；把有重复输入集合称为“多重集” 。 排列和组合一直是组合数学研究的重点，而多重集的排列又在排列问题中占有很大的比重 ， 生活中也有很多实际问题与多重集的排列密切相关。有关全排列的问题，早在我们高中的学习中就有过接触，对于有 N 个完全不同的元素的集合，一共有 N! 个排列。这是通常意义下的

13、全排列。 元素可以重复出现的集合称为多重集合或者多重集 ， 某元素重复出现的 次数称为该元素的重复度。例如，在多重集合 a， a， b， b， b， c， d中， a， b， c， d的重复度分别为 2， 3， 1， 1。因而多重集不能算严格意义上的集合。 很多科学 领域 ，尤其是 在 计算机和数学会经常遇到字符串全排列问题，需要穷举某个问题中所有可能出现情况，而且通常情况下是多重集并且要求无重复的输出 ，对多重集的研究势在必行。 如今全排列不仅在基础数学研究中具有极其重要的地位，在其它的学科如计算机科学，编码和密码学，统计科学，物理电路设计，化学，生物 DNA 序列等各种领域都有重要应用。

14、排列 产生的历史可以追溯到 十六世纪五十年代 ， 教堂中的牧师计算几口大钟不同的撞击顺序来产生各式的音乐效果。 早在 1960 年就有这一领域算法的总结性文章出现 13。 图灵奖获得者 Donald E. Knuth 在其经典著作计算机程序设计艺术一书中写道 50：“事实上，排列(permutations)问题在计算机领域 非常 重要。 Vaughan Pratt 提议直接把它们叫做 perms。如果Pratt 的建议得以实施，那么计算机的教科书的厚度将变得薄一些 (相应书的价格也会便宜一点 )”。虽然 Knuth 语带幽默，但由此可见排列在计算机领域出现的频率 之高。正是因为排列问题如此重要

15、，所以一直以来有众多的研究人员致力于该问题的解决。 普林斯顿大学计算机系 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 算法的另一种实现 ; 同

16、样是在厦门大学软件学院本科毕业论文 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 algor

17、ithms1116181922252930与 Random permutations1323242731。以上这些算法仅能解决无重复输入的 单集 排列 问题。 多重集 (Multiset)输入是一个相对较难的问题，不少研究者一直在寻求一个高性能的算法45384054。 多重集的排列一般是按字典序给出。另一 种常见的排列顺序是 Gray code，在Gray code 的排列中相邻的两个排列中仅有两个元素的位置不同。 James F. Korsh 和 Paul S. Lipschutz在 Johnson算法的基础上结合 Lehmer1324的思想得到第一个使用少循环的多重集排列产生算法 4。 在

18、求解多重集排列问题时传统算法为防止重复输出而保存大量纪录信息，许多研究人员投入 精力 简化纪录信息的保存和判断验证过程，也产生了许多精妙的算法。但这些算法都始终没有突破通过保存和判断信息来防止重复输出的思维藩篱。 而且大多数发表 的论文都没有一个详细，标准的模拟和比较。最近 的论文 Takaoka10与 Korsh9相比较，但是仅仅使用了 3， 3， 3， 3， 3和 2， 3， 5， 2， 3，事实上，仅仅使用几个测试案例是不足以证明一个算法的优越性能的。 厦门大学软件学院本科毕业论文 3 第二章 多重集排列的相关定义 2.1 多重集排列的理论基础 定义 ：广义上讲，我们把元素总个数 (包括

19、计算重复元素 )为 N 的集合 S看作是一个多重集，其中有 k 个不同的元素，它们的重复度分别为 n1 , n2 , , nk 。因此， N = n1+ n2 + nk ，当 N=k时， S 则成为一个 单集 ，因为 n1 = n2 = nk = 1，它是一个所有元素都不相同的多重集。 2.2 关于多重集排列的定理 定理 ：对于多重集 S，其元素总个数为 N(包括计算重复元素 )，有 k 个不同的元素，其重复度分别为 n1 ,n2 , , nk ，且 N = n1+ n2 + nk 。那么该多重集全排列个数有 12!()! !. !kNSkn n n (2-1) 证明：可以将这个问题看作：将

20、N 个元素的集合划分成 k 个被做标签的盒子 B1 ,B2 , ,Bk的方式数。其中盒 1含有 n1 个元素 ， 盒 2含有 n2 个元素 ， ， 盒 k 含有 nk 个元素。 首先选取 n1 个元素放入第一个盒子 ， 然后从剩下 N-n1 个元素中取 n2 个元素放入第二个盒子 ， 然后从剩下的 N-n1-n2 个元素中取 n3 个元素放入第三个盒子 ， 依此类推 ， 最后将 N-n1- n2- -nk-1 nk个元素放入第 k 个盒子。由乘法原理 ， 进行选择的总方法数为 1 2 11211 32. kkN n n nN n nNnNn nnn ， 即 12! !. !kNn n n 。

21、由于输入元素个数为 N 的全排列 ， 其输出的规模为 N！ 。因问题本身固有的内 在特点，其厦门大学软件学院本科毕业论文 4 时间复杂度中也必为 O(Cn!)其中 C 为常数（第 四 部分有时间复杂度的 详细分析 ）。 对于 长度为 17的字符串 ，全排列数 17！ = 355687428096000，三百万亿种。假设 计算机 一秒钟 可以 输出三百万种 ， 全部输出也要一亿秒钟 ，也就是说需要 3年零 2个月的时间。 所以 即使 是 20 个元素的集合 要 计算出的所有排列在人类可以接受的时间内 基本上 不可能。 但是 在科学研究中确实可能遇到较大规模的排列需求，除了配置高性能的计算机外找到

22、一个高性能的排列算法就显得非常必要。可见对全排列的研究，即使是一点点的提高，都会产生重大的影响 。在我们提出的平均时间方法测试下，本文的算法与所有已存在的 Multiset Permutation 比较，速度至少是它们的 3倍；在已经研究多年的 Pure Permutation 领域，本算法也比同类算法的速度快0.3 倍之上。 表 1 不同性能计算机在各种输入规模下进行排列所需时间 N 排列的个数 百万 /秒 十亿 /秒 万亿 /秒 10 3628800 11 39916800 几秒 12 479001600 几分钟 13 6227020800 几小时 几秒 14 87178291200 天

23、分钟 15 1307674368000 几周 几分钟 16 20922789888000 几个月 几小时 几秒 17 355687428096000 几年 几天 几分钟 18 6402373705728000 几个月 几小时 19 121645100408832000 几年 几天 20 2432902008176640000 月 微不足道 的等待 时间上 几乎不可能 厦门大学软件学院本科毕业论文 5 第三章 经典字符排列 算法 分析 全排列的生成算法 即 对于给定的字符集 ， 用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 由于我们使用 Mapping数组把 任何 n 个字符集的排列与

24、 1 n 的 n 个数字一一对应 起来 ，因 而 就以 n 个数字的排列为例说明 几种常见的 排列生成 方法 。 n 个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从它的前驱经过变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。 全排列的生成法通常有以下几种： 3.1 字典序法 字典序法中，对于数字 1， 2， 3 ， n 的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的 。例如对于 4 个数字的排列 1234 和 1243，排列 1234 在前，排列12

25、43 在后。按照这样的规定， 4个数字的所有的排列中最前面的是 1234，最后面的是 4321。 字典序算法如下： 设 P 是 1 n的一个全排列 : 1 2 1 1 1 1. . . . . . . . .j j j k k k np p p p p p p p p p 经过以下步骤即可得到该排列的后继排列： 1. 从右端开始，找出第一个比右边数字小的数字的序号 j，即 j = maxi |Pi Pj； 3. 对换 Pi， Pk； 4. 再将 Pj+1 Pk-1PkPk+1Pn倒 置； 这 样可以得到 排列 P 的下一个排列。 1 2 1 1 1 1 . . . . . . . . .j j

26、 n k k k jp p p p p p p p p p 厦门大学软件学院本科毕业论文 6 例如 839647521 是数字 1 9 的一个排列。从它生成下一个排列的步骤如下： 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

27、 Integer, j As Integer OutL P i = n - 1 Do While i 0 If P( i ) P( i + 1 ) Then For j = n To i + 1 Step -1 /从排列右端开始 If P( i ) P( j ) Then Exit For /找出递减子序列 Next Swap P( i ), P( j ) /将递减子序列前的数字与序列中比它大的第一个数交换 For j = n To 1 Step -1 /将 后面 排列倒 置 i = i + 1 If i j Then Exit For Swap P( i ), P( j ) Next OutL P /输出一个排列 i = n End If i = i - 1 Loop End Sub Swap P( i ), P( j )是交换两个元素的子过程， OutL p 是输出排列的子过程。 3.2 递增进位 制 数法 在递增进位制数法中，从一个排列求另一个排列需要用到中介数。中介数是计算排列的中间环节。已知一个排列，要求下一个排列，首先确定其中介数，一个排列的后继，其中介