資源描述：
《多重集的全排列算法研究-畢業(yè)論文.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、廈門大學(xué)本科畢業(yè)論文多重集的全排列算法研究[摘要]字符串的全排列問(wèn)題是一個(gè)非常有趣的數(shù)學(xué)問(wèn)題并且有悠久的歷史，本文提出了一種新的并且經(jīng)過(guò)模擬證明是最快的全排列算法。對(duì)于一個(gè)長(zhǎng)度為N的字符串來(lái)說(shuō)，如果它有k個(gè)不同的字符，每個(gè)字符重復(fù)出現(xiàn)的次數(shù)分別為：,....,當(dāng)這些數(shù)不全為1時(shí),我們稱其為輸入有重復(fù)的多重集字符串,它們的全排列問(wèn)題也因此被稱為多重集字符串的全排列問(wèn)題。若==....=，則每個(gè)字符出現(xiàn)的次數(shù)均為1，我們稱其排列為輸入無(wú)重復(fù)的單純集全排列問(wèn)題。對(duì)這兩種不同的排列，歷史上均出現(xiàn)過(guò)很多經(jīng)典算法。如對(duì)于單純集全排列，著名算法大師Sedgewick在其著作“permuta
2、tiongenerationmethods”[3]中指出，名為Heap[1]的算法是遞歸中最快的，而Ives[2]算法是迭代中最快的。對(duì)于多重集來(lái)說(shuō)，Ruskey[8]、ConstantTime[4]算法是比較快的。在這些與之比較的算法中，本文將著重介紹經(jīng)典的單純集全排列算法Ives,JohnsonandTrotter和多重集全排列算法ConstantTime。與傳統(tǒng)的全排列算法或者只產(chǎn)生多重集的全排列或者只產(chǎn)生單純集的全排列不同，本文的算法對(duì)于輸入無(wú)重復(fù)的單純集以及輸入有重復(fù)的多重集字符串均能快速產(chǎn)生正確的全排列。我們引入一個(gè)自然數(shù)數(shù)組：Mappings[]，將各個(gè)不同的輸
3、入字符一對(duì)一映射到這個(gè)連續(xù)的自然數(shù)數(shù)組，排列過(guò)程中僅對(duì)這個(gè)自然數(shù)組進(jìn)行操作，在適當(dāng)?shù)臅r(shí)機(jī)對(duì)數(shù)組元素?fù)Q位，從而不斷縮小子問(wèn)題的取值空間，實(shí)現(xiàn)無(wú)需進(jìn)行大量判斷自動(dòng)排除重復(fù)輸出。最后排列的結(jié)果根據(jù)自然數(shù)與字符對(duì)應(yīng)關(guān)系得到。通過(guò)對(duì)長(zhǎng)度N=10,11,12,13,14,15,16,和17的輸入進(jìn)行模擬并且和其它11種經(jīng)典的單純集全排列算法和多重集全排列算法所用的時(shí)間加以比較[1][2][3][4][5][6][7][8][9][10]，本文的算法TWDRI是速度最快的，在占用內(nèi)存方面也很有優(yōu)勢(shì)，平均內(nèi)存不到800K。此外，我們還介紹了一種對(duì)于多重集輸入的所有可能排列測(cè)試其平均排列時(shí)間的
4、算法。[關(guān)鍵詞]多重集全排列全排列的產(chǎn)生最快字符串的全排列第43頁(yè)共43頁(yè)廈門大學(xué)本科畢業(yè)論文AResearchintoMultisetPermutationAlgorithm[Abstract]Thepermutationofastringisaninterestingmathematicalproblemandhasalonghistory.Inthispaper,IwillintroducetheTWDRIalgorithm,anewalgorithmwhichisdifferentfromothers.Throughoursimulationandcomparison
5、withotherelevenalgorithms,wehaveprovedthatouralgorithmisthefastestalgorithmamongthem.SupposeastringwhoselengthisN.Iftherearekdifferentcharacters,eachhascount,…,respectively.Ifallthesecountsdon’tequalto1,wecallthestring“multisetstring”,thereforetheirpermutationsarecalled“multisetpermutations
6、.”If==…..=,thenthecountforeachcharacteris1,wecalltheirpermutations“purepermutations.”Manyalgorithmswereintroducedforthesetwokinds’permutations.Forthepurepermutation,thefamousalgorithmscholarSedgewickdescribedinhisbook“permutationgenerationmethods”thattheHeapalgorithm[1]wasthefastestrecursiv
7、eexchangealgorithmwhileIves[2]wasthefastestiterativeexchangealgorithm.Forthemultisetpermutations,Ruskeyalgorithm[8]andConstantTimealgorithm[4]weretwofasteralgorithms.Amongthesealgorithms,Iwanttoemphasizeonthepurepermutationalgorithms:Ives,JohnsonandTrott
