資源描述：
《多重集全排列算法研究------畢業(yè)論文.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。
1、廈門大學本科畢業(yè)論文本科畢業(yè)論文(科研訓練、畢業(yè)設(shè)計)題目：多重集全排列算法研究姓名：學院：軟件學院系：軟件工程系專業(yè)：軟件工程年級：學號：指導教師（校內(nèi)）：職稱：年月26廈門大學本科畢業(yè)論文多重集全排列算法研究[摘要]全排列算法按處理輸入的能力可分為集合(set)排列算法和多重集(multiset)排列算法。多重集中一個元素可多次出現(xiàn)，多重集排列算法不會產(chǎn)生重復的排列。本文介紹了一種新的全排列產(chǎn)生算法。該算法能同時解決集合排列問題和多重集排列問題；適用于各種不同字符的輸入情況，具有通用性。與已有算法不同，新算法不采用交換產(chǎn)生排列而是
2、先計算輸入中不同元素(distinctelement)的出現(xiàn)次數(shù)(multiplicity)，再將各個不同輸入字符一對一映射到連續(xù)的自然數(shù)集合。排列過程中僅對自然數(shù)數(shù)組進行操作，遞歸求解時能不斷縮小子問題的取值空間，實現(xiàn)無需進行大量判斷自動排除重復輸出。最后排列結(jié)果根據(jù)自然數(shù)到字符的逆映射得到。文章選取經(jīng)典全排列算法進行分析和比較。我們進行了大量的模擬，測試了從10位到17位的輸入情況，與已知最新和最快的算法進行比較[1][2][3][4][5][6][7][8][9][10]，新算法速度是世界上已知最快多重集排列算法的3倍，同時也比
3、已知最快集合排列算法快30%。[關(guān)鍵詞]多重集全排列算法26廈門大學本科畢業(yè)論文AResearchintoMultisetPermutationAlgorithm[Abstract]Permutationalgorithmscanbedividedintotwogroups:setpermutationalgorithmsandmultisetpermutationalgorithms.Multisetdiffersfromasetinthateachmemberhasamultiplicity.Multisethasrepeated
4、elements,suchas{a,a,b,b,b,c}.WeconsideranycharacterstringoflengthNasamultiset,whichhaskdifferentcharacters,eachhascountn1,n2,…,nk,respectively.Clearly,N=n1+n2+…+nk.Fortheinputstring,themultisetpermutationgeneratesallpossiblepermutationswithoutredundancy.WhenN=k,itisapur
5、epermutationsincen1=n2=…=nk=1.Numerousalgorithmswereproposedinpublicationsincetheresearchhistoryofthisproblemisquitelong.Unfortunately,multisetpermutationistougherproblemwithfeweroutcomes.Anewpermutationalgorithmisdescribed.Thisalgorithmcanbeappliedinsetandmultiset.Inbo
6、thcase,ithasahighperformance.Thenewalgorithmfirstcalculatesthefrequencyofeachdistinctelementintheinput,andthenmapsthedistinctelementstonaturalnumbers.Intheprocessofpermutation,itonlydealswithnaturalnumbers.TheTWDRIalgorithmeliminatesunnecessaryswitchesandreducestheloopt
7、imesinordertospeedupthepermutationandtoreducememoryconsumption.Wealsocomparethenewalgorithmwithseveralotheralgorithms.Thispaperanalysesseveralclassicalalgorithmsinthisfield.WeevaluateourpermutationtimeandmemoryconsumptionbysimulatingstringswithlengthN=10,11,12,13,14,15,
8、16,and17,respectively.WecalculateaveragemultisetpermutationtimeforallpossibleNNinputswitheachfixedlengthNabove
