資源描述：
《多重集全排列算法研究------畢業(yè)論文.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、廈門大學(xué)本科畢業(yè)論文本科畢業(yè)論文(科研訓(xùn)練、畢業(yè)設(shè)計)題目：多重集全排列算法研究姓名：學(xué)院：軟件學(xué)院系：軟件工程系專業(yè)：軟件工程年級：學(xué)號：指導(dǎo)教師（校內(nèi)）：職稱：年月26廈門大學(xué)本科畢業(yè)論文多重集全排列算法研究[摘要]全排列算法按處理輸入的能力可分為集合(set)排列算法和多重集(multiset)排列算法。多重集中一個元素可多次出現(xiàn)，多重集排列算法不會產(chǎn)生重復(fù)的排列。本文介紹了一種新的全排列產(chǎn)生算法。該算法能同時解決集合排列問題和多重集排列問題；適用于各種不同字符的輸入情況，具有通用性。與已有算法不同，新算法不采用交換產(chǎn)生排列而是先計算輸入
2、中不同元素(distinctelement)的出現(xiàn)次數(shù)(multiplicity)，再將各個不同輸入字符一對一映射到連續(xù)的自然數(shù)集合。排列過程中僅對自然數(shù)數(shù)組進(jìn)行操作，遞歸求解時能不斷縮小子問題的取值空間，實現(xiàn)無需進(jìn)行大量判斷自動排除重復(fù)輸出。最后排列結(jié)果根據(jù)自然數(shù)到字符的逆映射得到。文章選取經(jīng)典全排列算法進(jìn)行分析和比較。我們進(jìn)行了大量的模擬，測試了從10位到17位的輸入情況，與已知最新和最快的算法進(jìn)行比較[1][2][3][4][5][6][7][8][9][10]，新算法速度是世界上已知最快多重集排列算法的3倍，同時也比已知最快集合排列算法
3、快30%。[關(guān)鍵詞]多重集全排列算法26廈門大學(xué)本科畢業(yè)論文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
