資源描述：
《多重集全排列算法研究-畢業(yè)論文.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、多重集全排列算法研究[摘要]本文提出一種新的全排列產(chǎn)生算法——TWDRI。該算法能同時(shí)解決一般的無重復(fù)輸入的單集(purepermutation)問題和輸入有重復(fù)的多重集(multisetpermutation)問題，而且適用于各種不同字符輸入情況，具有通用性。與已有算法不同，本文的新算法首先根據(jù)輸入字符的頻率預(yù)排序，再將各個(gè)不同輸入字符一對(duì)一映射到連續(xù)的自然數(shù)數(shù)組。排列過程中僅對(duì)該數(shù)組進(jìn)行操作，在適當(dāng)?shù)臅r(shí)機(jī)對(duì)數(shù)組元素?fù)Q位，從而不斷縮小子問題的取值空間，無需進(jìn)行大量判斷就可以自動(dòng)排除重復(fù)輸出。最后排列的結(jié)果再根據(jù)自然數(shù)與字
2、符對(duì)應(yīng)關(guān)系得到。而且對(duì)于多重集，本文提出了一種新的評(píng)估多重集算法性能的方法——平均時(shí)間(averagetimeofmultisetpermutations)，對(duì)于長度為N的輸入，由它產(chǎn)生的所有的NN種情況都進(jìn)行測試。我們進(jìn)行了大量的模擬，測試了從10位到17位的輸入情況，與已知的算法進(jìn)行了比較[1][2][3][4][5][6][7][8][9][10]，本文提出的算法表現(xiàn)出優(yōu)秀的性能，比已有算法使用更快的時(shí)間得到所有排列結(jié)果。[關(guān)鍵詞]全排列多重集算法31AResearchintoMultisetPermutationA
3、lgorithm[Abstract]Weintroduceanewpermutationgenerationmethod——TWDRI.Itcansolvebothproblemsthegeneralnon-duplicatedinput(purepermutation)andtheduplicatedinput(multisetpermutation).Besides,itcanhandleallkindsofdifferentcharactersinput.Comparedwiththeexistingalgorith
4、ms,thisnewalgorithmisbasedonthefrequencyofinputcharacters.Itsortsthecharactersfirstbytheirfrequencythenmapthemtoanaturalnumbersarray(Mapping[])one-by-one.Whengeneratingthepermutation,itjustmanipulatesthearrayelementratherthancharacters.Duringtheprocess,wedeletethe
5、arrayelementinordertoshrinkthevalue-spaceofthesub-problemandreducelotsofestimationforavoidingrepeatedoutput.Atlast,wewillgettheresultsaccordingtheMapping[]totransformthenaturalnumberstotheinitialcharactersthatweinput.Forthemultisetpermutation,wealsointroduceanewme
6、thodtoestimatesuchalgorithms,whichiscalledAverageTimeofMultisetPermutation.WeevaluateourpermutationtimeandmemoryconsumptionbysimulatingstringsfromlengthN=10to17,respectively.WecalculateaveragemultisetpermutationtimeforallpossibleNNinputswitheachfixedlengthNabove.W
7、ecompareourresultswiththefastestknownand/orwell-knownalgorithms[1][2][3][4][5][6][7][8][9][10]indetail.Andthisalgorithmshowsgreatperformance,ituselesstimethanallthealgorithmthatwehavementioned.[Keywords]permutationmultisetalgorithm31目錄第一章引言1第二章多重集排列的相關(guān)定義32.1多重集排列的
8、理論基礎(chǔ)32.2關(guān)于多重集排列的定理3第三章經(jīng)典字符排列算法分析53.1字典序法53.2遞增進(jìn)位制數(shù)法63.3遞減進(jìn)位制數(shù)法83.4鄰位對(duì)換法(格雷碼序法)103.5元素增值法(N進(jìn)制法)113.6遞歸類算法12第四章TWDRI算法介紹154.1算法整體流程圖154.2算法特色164.3時(shí)間復(fù)雜度分析1
