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

《多重集全排列算法研究 -- Alternative算法概述及测试比较》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、0位到17位的输入情况，与世界上已知最快的和最近的算法进行比较。通过数据分析表明，TWDRI算法速度是世界上已知最快多重集排列算法的2倍。[关键词]多重集排列算法TWDRIVIIIAbstractTheresearchingofthepermutationalgorithmalreadyhadgloriousphaseofhistories.Afterlooksbackintoandhasappraisedinsimplythehistorytheclassicalpermutationalgorithm,proposedonekindofnewpermutationa

3、lgorithmTWDRI.Thisalgorithmcansimultaneouslysolvenewpermutationtechniqueformultisetpermutationsandpurepermutation.Isdifferenthasthealgorithminthemajoritypermutationonlytobeabletoprocessthevaluethecharacteristic,thisalgorithmissuitableforeachkindofdifferentcharacterinputsituation,hastheve

4、rsatility.Forcantheobjectiveevaluationexistingeachkindofpermutationalgorithmperformance,theselectionclassicspermutationalgorithmcarryontheanalysisandthecomparison,andhascarriedonthemassivesimulations,hastestedfrom10to17inputsituations,knownquickestandtherecentalgorithmcarriesonthecompari

5、sonwiththeworld.IndicatedthroughthedataanalysisthattheTWDRIalgorithmspeedisintheworldknownquickestmultisetpermutationalgorithm2times.[Keywords]multiset；permutation；algorithm；TWDRIVIII目录第一章引言1第二章研究背景22.1单重集全排列定义22.2多重集全排列定义22.3多重集排列的研究历史3第三章历史上主要的排列算法53.1JohnsonandTrotter算法53.2Ives迭代算法73.

6、3基于格雷码顺序的多重集排列算法93.4Heap递归算法103.5Alternative算法113.6ConstantTime算法13第四章TWDRI算法154.1主要流程图154.2算法时间复杂度154.3TWDRI算法的优点17第五章分析与比较195.1基于随机输入的平均时间计算模型195.2计算模型的推导过程195.3平均时间计算公式215.4比较结果225.4.1多重集算法的时间和内存开销比较235.4.2多重集算法在非重复输入的情况下的时间和内存占用比较245.4.3TWDRI算法和其它单重集排列算法的时间和内存比较25VIII5.4.4TWDRI算法与其它多

7、重集排列算法的速度比26结论29致谢语30[参考文献]31VIIICONTENTSCHAPTER1INTRODUCTION1CHAPTER2BACKGROUND22.1TheDefinitionofPure22.2TheDefinitionofMultiset22.3TheStudyHistoryofMultiset3CHAPTER3CLASSICALALGORITHM53.1JohnsonandTrotterAlgorithm53.2Ives'sIterativeAlgorithm73.3MultisetPermutationAlgor