1、 本科毕业论文 (科研训练、毕业设计 ) 题 目： 多重集全排列算法研究与 汇编 分析 姓 名： 学 院：软件学院 系：软件工程系 专 业：软件工程 年 级： 学 号： 指导教师 ： 职称： 年 月 I 摘 要 全排列 产生 算法已有悠久的历史，其涉及的理论研究领域和应用范围相当广泛。数百年来，对全排列问题的研究一直都未间断，计算机 的 诞生 使该问题得到了更多的关注且有了巨大的发展 。本文对全排列算法前进过程中产生的算法进行了简要的分类介绍，并对各类中的经典算法进行了分析说明。 随后 提出一种全新的全排列产生算法 TWDRI,该算法能同时对多重集和单集进行全排列，并且性能优 异 。一个对全排
2、列算法进行比较的平 均时间测试模型将在文中 给出 ， 用以证明 TWDRI算法的优越性 。 经过大量模拟，其结果显示 TWDRI算法比世界上现有的其他全排列算法速度 都 快。 为 了 在理论上 进一步论证 该 比较 结果 的科学性与正确性，一个在汇编层次分析 算法 的 设想在文中提出， 其探索也 取得了初步的成果。 关键词 ： 多重集 全 排列 算法 汇编 II Abstract Permutations generation enjoys a long historical standing. It touches many theoretical research and applicat
3、ion domains. For centuries, the study on permutation generation has never been ceased. Further more, more attentions have been paid on it since the invention of computers, thus tremendous development of it has been achieved. In this thesis, the whole permutation generation algorithms that appeared i
4、n history will be introduced by category， and the classic algorithm of each kind will also be described respectively. Then a new algorithm for permutation generation named TWDRI will be put forward, which can be simultaneously applied to multiset and singleset with excellent performance. Moreover, a
5、 calculation model of average time will be introduced, in order to compare all the permutation generation algorithms and prove the superiority of TWDRI algorithm. After a lot of simulations, the results show that TWDRI algorithm runs faster than the other existing world-wide permutation generation a
6、lgorithms. To further prove that this comparison is both scientific and correct in theory, an assumption based on assembly analysis is also given, and has gained preliminary results in real practice. Key words： multiset; permutation; algorithm; assembly III 目录 第一章 绪论 . 1 1.1 课题背景与意义 . 1 1.2 主要研究内容 .
7、 1 1.3 本文结构 . 2 第二章 全排列概述及经典算法 . 3 2.1 基本定义 . 3 2.2 按字典序排法 . 3 2.3 格雷码与相邻交换 . 5 2.4 Loopless 算法 . 7 2.5 递归算法 . 8 2.6 迭代算法 . 10 2.7 TWDRI 算法 . 12 第三章 平均时间测试模拟比较 . 14 3.1 平均时间测试模型 . 14 3.1.1 模型介绍 . 14 3.1.2 平均时间测试程序 . 17 3.2 模拟比较结果 . 18 3.2.1 比较方案说明 . 19 3.2.2 多重集算法的平均时间和内存花销比较 . 20 3.2.3 所有算法同一单集输入下的
8、时间和内存花销比较 . 21 3.2.4 TWDRI 算法与其他算法的比较分析 . 23 第四章 汇编层次 分析 比较的探索 . 26 4.1 汇编层次比较的必要性 . 26 4.2 分析方案的选择 . 27 4.3 分析举例 . 27 第五章 总结与展望 . 31 致谢语 . 32 参考文献 . 33 IV Contents Chapter 1 Introduction . 1 1.1 Background and Construction . 1 1.2 Main Content . 1 1.3 Chapters Structure. 2 Chapter 2 Permutation Sum
9、mary and Classical Algorithms . 3 2.1 Basic Definition . 3 2.2 Lexicographic Permutation. 3 2.3 Grad Code and Adjacent Exchange . 5 2.4 Loopless Algorithm . 7 2.5 Recursive Algorithm . 8 2.6 Iterative Algorithm .10 2.7 TWDRI Algorithm .12 Chapter 3 Average Time Calculation Model and Comparison .14 3
10、.1 Average Time Calculation.14 3.1.1 Introduce The Model .14 3.1.2 Program of Average Time Calculation Model .17 3.2 Comparison .18 3.2.1 Programme Introduction.19 3.2.2 Compare Avaerage Time and Memory of Multiset Permutation .20 3.2.3 Compare Avaerage Time and Memory of Pure Permutation .21 3.2.4
11、Compare TWDRI with Other Algorithms .23 Chapter 4 The Comparision Based on Assembly .26 4.1 Necessity of Comparision Based on Assembly .26 4.2 Choice of The Analysis Method .27 4.3 Example .27 Chapter 5 Conclusings and Future Work .31 Acknowledgements .32 References .33 厦门大学本科 毕业论文 1 第一章 绪论 排列 一个即贴身
12、而又遥远的问题。从娱乐游戏中的扑克牌到人类基因碱基对的排列，从七个音符组合的美妙音乐到化学领域中微小的原子组合的顺序无论是我们日常生活中随处可见的，还是科学家努力探索的各种科技前沿问题，都常常需要排列组合的知识。 1.1 课题背景与意义 全排列问题涉及的领域相当 广泛，特别是 在众多的数学问题中都出现了全排列的身影，特别是在离散数学、概率论和图论中，全排列问题也是数学中最基本的问题之一。以数学为理论依托的计算机理论科学对全排列进行重点研究更是理所当然。再加上随着计算机运算能力的提 升，其运用范围也越来越广，一些需要计算机解决的问题（ TSP 问题 、图的同构问题、密码破译、运筹安排问题等）实际
13、上都可以归结为产生全排列的过程，从这个意义上讲，全排列产生的研究也必然引起众多计算机领域学者的关注。 全排列问题的解是按输入长度 N 的指数级规模增长的，对于较大的 N 产生出 所有排列将是不太可能的。尽管计算机的计算能力在不断增长，较大集合 的全排列产生问题仍不能得到高效的解决，寻找一个高性能的全排列产生算法是十分有必要。在这个探索的过程中，也涌现出很多的高性能的精妙的算法，使这个领域得到不断的发展。 1.2 主要研究内容 通过收集和查阅全排列方面的相关论文，本文对之前发表的全排列算法进行了分析总结，对全排列算法研究领域的几个主要类型的算法特点进行了归纳 ，特别是对一些经典的算法进行了深入的
14、研究 。在 此 基础之上，提出了一个全新的解决多重集全排列的新算法 TWDRI 算法。 很多算法还没有经过可靠并且详尽的数据模拟和比对就给出了 算法优劣的结论 ，为了克服这缺陷，文中提出一个平均时间测试模型。通过平均测试模型的模拟测试比较，证明了 TWDRI 的速度是目前世 界 上最快的全排列算法，文中也将给出数据图表。 一个在汇编层面分析比较算法的 设想也相继被提出 ，在这方面的探索也得到了初步成果。 厦门大学本科 毕业论文 2 1.3 本文结构 第二章 介绍全排列算法的几个主要分类，概述其主要的特点，并且将给出各个分类的典型算法 ，又特别介绍了本团队新的独创性算法 TWDRI。 第三章将
15、着重对众多算法的性能进行比较：提出了公平的测试模型，并且将大规模的实际模拟结果以图表的形式进行对比分析。 在第四章中 ， 将 提出在汇编层面分析全排列算法的构想，并初步进行了探索。 最后，对该研究课题进行了总结 与展望。 厦门大学本科 毕业论文 3 第二章 全排列概述及经典算法 本章将介绍全排列 产生方法 的 几个主要的 分类，以及 各种分类 的一些 经典的算法，并对算法进行分析 说明 。 2.1 基本定义 在详细介绍全排列相关问题及 进行 算法讨论之前， 有必要先介绍一下全排列的一些基本的定义 ： 定义 1 单集 ： 对于一个长度为 N 的字符串来说，如果它有 k 个不同的字符，每个字符重复
16、出现的次数均为 1，即 N=k, 我们称这样的输入为单集 。 定义 2 多重集 ： 对于一个长度为 N 的字符串来说，如果它有 k 个不同的字符，每个字符重复出现的次数分别为： n0, n1, , nk-1（这些数不全为 1） ，则 称这样的输入为多重集。 定义 3 全排列 ： 对于给定一个长度为 N 的字符串，如果是单集，给出 N！ 个长度为 N 的 由所给字符串变换顺序产生的 字符串，且任意两个字符串都不相同，则称为单集的全排列；如果是 k 个不同的字符，每个字符重复出现的次数分别为： n0, n1, , nk-1 (N= n0+ n1+nk-1)的 多重集， 给出0 1 1! !. !k
17、Nn n n个 长度为 N 的 由所给字符串变换顺序产生的 字符串，且任意两个字符串都不相同，则称为多重集的全排列 。 对于单集 1， 2， 3，其全排列为 ： （ 2） 132 （ 3） 213 （ 4） 231 （ 5） 312 （ 6） 321 以 1， 2， 2， 3作为多重集的实例，得出的全排列为 ： （ 1） 1223 （ 2） 1232 （ 3） 1322 （ 4） 2123 （ 5） 2132 （ 6） 2213 （ 7） 2231 （ 8） 2312 （ 9） 2321 （ 10） 3122 （ 11） 3212 （ 12） 3221 2.2 按字典序排法 字典序是排列中最经
18、典的算法，在各种排列场合下被广泛引用。字典序排列法对字符串的出现顺序作了严格的规定，因此要实现从一个排列得到它的下一个排列通常需要较多的操作。 厦门大学本科 毕业论文 4 以字符串 ABC 为例，如果按字典序产生全排列，则顺序应该是：ABC,ACB,BAC,CAB,CBA。 给一个不太严格的定义即对于给出的所有全排列中的任意两个字符串 P1、 P2，设从左到右第一个不相同字符位置为 i， a 为 P1 在 位置 i 上的字符， b 为P2 在 位置 i 上的字符，如果 aal al+1 an。 在 j 的值接近于 n 时通过流水线化操作可以算法 L 运行得更快，可以用以下步骤 L2L4.1代替
19、算法 L 中的 L2 至 L4。 算法 L 的改进如下： Optimize the Algorithm L 假设多重集长度 n 不小于 3 L2 置 y值为 an-1， z 的值为 an。如果 yz则置 a n-1值为 z, a n值为 y， 并返回 L1 L2.1 置 x值为 a n-2, 如果 x y，则转到 L2.2。否则如果 xz， 则置 (an-2,an-1,an)值为 (z,x,y),如果 x z,则置 (an-2,an-1,an)值为 (y,z,x)。 L2.2 置 j 值为 n-3， y值为 aj。如果 y x,置 j 值为 j-1, x 值为 y， y值为 aj，厦门大学本科
20、 毕业论文 5 并重复直到 yx 为止。如果 j=0 则结束。 L3 如果 yz， 则置 aj值为 z， aj+1 值为 y， an 值为 x 并跳转到 L4.1。 L3.1 置 l 值为 n-1；如果 y al， l 重复减 1直到 yal 为止，然后置 aj值为 al，al 值为 y。 L4 置 an 值为 a j+1， a j+1 值为 z。 L4.1 置 k值 为 j+2， 1 值为 n-l。然后如果 kl，交换 ak和 al。 k 加 1， l 减 1，重复直到 k l。返回 L1。 2.3 格雷码与 相邻交换 对于全排列的产生， 很 自然 会想到 的办法是通过交换当前输出字符串中的
21、元素来得到下一种输出 。 要产生每种排列时，需要交换的次数是否仅仅需要 1 次？ 交换是两个元素的交换，那么这两个元素之间应该存在什么样的关系，才能使得 交换之前的准备 操作的次数尽量的少呢？在说明这个疑问之前，先简单分绍一个新的概念 格雷二进制码。 格雷二进制码 (图 2 - 1)是以这样一种方式来列出所有 2n 个 n 位的串，即它以一种简单和规则的方式，每次仅改变一个二进位。 可能引起数字量发生变化时，格雷码仅改变一位，这样与其它编码同时改变两位或多位的情况相比更为可靠 ，且操作较少 。 图 2 -1 格雷二进制码 类似的方法，我们在生成全排列时 是否也存在呢？假设存在，那 么我们可以对于 1，2， n-1构造这样的序列，然后将数 n 插入到每个排列中的 n 个可能的位置。例如当 n=4时，把 4 插入到所有 4 个可能的位置时，则可从序列（ 123,132,312,321,231,213）得到下列
