资源描述：
《多重集全排列算法研究------毕业论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、厦门大学本科毕业论文本科毕业论文(科研训练、毕业设计)题目：多重集全排列算法研究姓名：学院：软件学院系：软件工程系专业：软件工程年级：学号：指导教师（校内）：职称：年月26厦门大学本科毕业论文多重集全排列算法研究[摘要]全排列算法按处理输入的能力可分为集合(set)排列算法和多重集(multiset)排列算法。多重集中一个元素可多次出现，多重集排列算法不会产生重复的排列。本文介绍了一种新的全排列产生算法。该算法能同时解决集合排列问题和多重集排列问题；适用于各种不同字符的输入情况，具有通用性。与已有算法不同，新算法不采用交换产生排列而是先计算输入
2、中不同元素(distinctelement)的出现次数(multiplicity)，再将各个不同输入字符一对一映射到连续的自然数集合。排列过程中仅对自然数数组进行操作，递归求解时能不断缩小子问题的取值空间，实现无需进行大量判断自动排除重复输出。最后排列结果根据自然数到字符的逆映射得到。文章选取经典全排列算法进行分析和比较。我们进行了大量的模拟，测试了从10位到17位的输入情况，与已知最新和最快的算法进行比较[1][2][3][4][5][6][7][8][9][10]，新算法速度是世界上已知最快多重集排列算法的3倍，同时也比已知最快集合排列算法
3、快30%。[关键词]多重集全排列算法26厦门大学本科毕业论文AResearchintoMultisetPermutationAlgorithm[Abstract]Permutationalgorithmscanbedividedintotwogroups:setpermutationalgorithmsandmultisetpermutationalgorithms.Multisetdiffersfromasetinthateachmemberhasamultiplicity.Multisethasrepeatedelements,suchas
4、{a,a,b,b,b,c}.WeconsideranycharacterstringoflengthNasamultiset,whichhaskdifferentcharacters,eachhascountn1,n2,…,nk,respectively.Clearly,N=n1+n2+…+nk.Fortheinputstring,themultisetpermutationgeneratesallpossiblepermutationswithoutredundancy.WhenN=k,itisapurepermutationsincen1=
5、n2=…=nk=1.Numerousalgorithmswereproposedinpublicationsincetheresearchhistoryofthisproblemisquitelong.Unfortunately,multisetpermutationistougherproblemwithfeweroutcomes.Anewpermutationalgorithmisdescribed.Thisalgorithmcanbeappliedinsetandmultiset.Inbothcase,ithasahighperforma
6、nce.Thenewalgorithmfirstcalculatesthefrequencyofeachdistinctelementintheinput,andthenmapsthedistinctelementstonaturalnumbers.Intheprocessofpermutation,itonlydealswithnaturalnumbers.TheTWDRIalgorithmeliminatesunnecessaryswitchesandreducesthelooptimesinordertospeedupthepermuta
7、tionandtoreducememoryconsumption.Wealsocomparethenewalgorithmwithseveralotheralgorithms.Thispaperanalysesseveralclassicalalgorithmsinthisfield.WeevaluateourpermutationtimeandmemoryconsumptionbysimulatingstringswithlengthN=10,11,12,13,14,15,16,and17,respectively.Wecalculateav
8、eragemultisetpermutationtimeforallpossibleNNinputswitheachfixedlengthNabove
