多重集的全排列算法的研究——算法归类分析.doc

《多重集的全排列算法的研究——算法归类分析.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本科毕业论文(科研训练、毕业设计)题目：多重集的全排列算法的研究——算法归类分析姓名：学院：软件学院系：软件工程系专业：软件工程年级：学号：指导教师：职称：年月摘要排列产生算法的研究在计算机发明之前已被人们所研究，其历史甚至可以追溯到三百年前之久。全排列算法按处理输入的能力可分为集合(set)排列算法和多重集(multiset)排列算法。多重集中一个元素可多次出现，多重集排列算法不会产生重复的排列。为了更方便区分，在文中分别叫做单重集和多重集排列。本文旨在对历史上一些经典的全排列算法进行分类总结的基础上，着重介绍一种新的全排列算法TWDRI，该算法能同时解

2、决集合排列问题和多重集排列问题；适用于各种不同字符的输入情况，具有通用性。并且介绍了从汇编的角度去分析新的算法和其他有代表性的若干算法的方法，从而可以从理论上去分析它们的优劣，最终得出新算法TWDRI具有效率最好的结论。关键词多重集；排列；算法；汇编；少循环VAbstractThepermutationhasthealgorithmresearchbeforethecomputerwasinvented,andithasbeenstudiedbypeople,itshistoryevenmaytrace300yearsago.Permutationalgo

3、rithmscanbedividedintotwogroups:setpermutationalgorithmsandmultisetpermutationalgorithms.Multisetdiffersfromasetinthateachmemberhasamultiplicity.Foramoreconvenientdiscrimination,theyarecalledthepurepermutationandthemultisetpermutationseparatelyinthearticle.Thisarticleisforthepurpo

4、setothehistoryinsomeclassicalpermutationalgorithmscarryingonthefoundationwhichtheclassificationsummarizes,introducedemphaticallyonekindofnewpermutationalgorithmTWDRI,thisalgorithmcansimultaneouslysolvethepurepermutationproblemandthemultisetpermutationquestions;andissuitableineachk

5、indofdifferentcharacterinputsituation.Italsohastheversatility.Andthisarticleanalyzesthenewalgorithmfromtheassemblyangleandotherwhichhastherepresentativecertainalgorithmdifference,thusanalyzestheirfitandunfitqualityfromthetheory,obtainsnewalgorithmTWDRItohavetheefficiencybestconclu

6、sionfinally.Keywordsmultiset；permutation；assemblyalgorithm；loopless目录V第一章绪论11.1课题的背景与意义11.1.1多重集排列的相关定义11.1.2多重集排列的研究历史21.1.3课题的意义31.2本文的主要工作41.3论文的主要结构4第二章全排列算法52.1递归算法52.1.1算法定义52.1.2算法特征52.1.3经典算法（heap算法）62.1.4分析总结72.2loopless算法72.2.1算法定义72.2.2算法发展82.2.3分析总结122.3GrayCode122.3.1

7、格雷码的定义122.3.2格雷编码的算法实现122.3.3在全排列的运用142.4汇编分析方法142.4.1MIX142.4.2MMIX15第三章TWDRI算法163.1主要流程163.2算法时间复杂度173.3TWDRI算法的通用性和创新性19第四章模拟比较214.1模拟测试214.2多重集算法的时间和内存开销比较224.3多重集算法在非重复输入的情况下的时间和内存开销比较234.4TWDRI算法和其它单重集排列算法的时间和内存比较244.5TWDRI算法与其它多重集排列算法的比较趋势分析25第五章总结与展望27致谢语28参考文献29VContentsC

8、HAPTER1INTRODUCTION11.1Background