資源描述：
《多重集全排列算法研究 -- Alternative算法概述及測試比較》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、本科畢業(yè)論文(科研訓(xùn)練、畢業(yè)設(shè)計)題目：多重集全排列算法研究--Alternative算法概述及測試比較姓名：學(xué)院：軟件學(xué)院系：專業(yè)：軟件工程年級：學(xué)號：指導(dǎo)教師：陳金柱職稱：年月VIII摘要全排列算法問題的研究已經(jīng)有很悠久的一段歷史。在簡單回顧和評價了歷史上經(jīng)典的排列算法之后，提出了一種新的全排列產(chǎn)生算法TWDRI。該算法能同時解決無重復(fù)輸入的單集問題和重復(fù)輸入的多重集問題。不同于大多數(shù)排列產(chǎn)生算法只能處理數(shù)值的特性，本算法適用于各種不同字符的輸入情況，具有通用性。為了能客觀評價現(xiàn)有各種排列算法的性能，選取經(jīng)典全排列算法進(jìn)行分析和比較，并且進(jìn)行了大量的模擬，測試了從1
2、0位到17位的輸入情況，與世界上已知最快的和最近的算法進(jìn)行比較。通過數(shù)據(jù)分析表明，TWDRI算法速度是世界上已知最快多重集排列算法的2倍。[關(guān)鍵詞]多重集排列算法TWDRIVIIIAbstractTheresearchingofthepermutationalgorithmalreadyhadgloriousphaseofhistories.Afterlooksbackintoandhasappraisedinsimplythehistorytheclassicalpermutationalgorithm,proposedonekindofnewpermutationa
3、lgorithmTWDRI.Thisalgorithmcansimultaneouslysolvenewpermutationtechniqueformultisetpermutationsandpurepermutation.Isdifferenthasthealgorithminthemajoritypermutationonlytobeabletoprocessthevaluethecharacteristic,thisalgorithmissuitableforeachkindofdifferentcharacterinputsituation,hastheve
4、rsatility.Forcantheobjectiveevaluationexistingeachkindofpermutationalgorithmperformance,theselectionclassicspermutationalgorithmcarryontheanalysisandthecomparison,andhascarriedonthemassivesimulations,hastestedfrom10to17inputsituations,knownquickestandtherecentalgorithmcarriesonthecompari
5、sonwiththeworld.IndicatedthroughthedataanalysisthattheTWDRIalgorithmspeedisintheworldknownquickestmultisetpermutationalgorithm2times.[Keywords]multiset；permutation；algorithm；TWDRIVIII目錄第一章引言1第二章研究背景22.1單重集全排列定義22.2多重集全排列定義22.3多重集排列的研究歷史3第三章歷史上主要的排列算法53.1JohnsonandTrotter算法53.2Ives迭代算法73.
6、3基于格雷碼順序的多重集排列算法93.4Heap遞歸算法103.5Alternative算法113.6ConstantTime算法13第四章TWDRI算法154.1主要流程圖154.2算法時間復(fù)雜度154.3TWDRI算法的優(yōu)點17第五章分析與比較195.1基于隨機(jī)輸入的平均時間計算模型195.2計算模型的推導(dǎo)過程195.3平均時間計算公式215.4比較結(jié)果225.4.1多重集算法的時間和內(nèi)存開銷比較235.4.2多重集算法在非重復(fù)輸入的情況下的時間和內(nèi)存占用比較245.4.3TWDRI算法和其它單重集排列算法的時間和內(nèi)存比較25VIII5.4.4TWDRI算法與其它多
7、重集排列算法的速度比26結(jié)論29致謝語30[參考文獻(xiàn)]31VIIICONTENTSCHAPTER1INTRODUCTION1CHAPTER2BACKGROUND22.1TheDefinitionofPure22.2TheDefinitionofMultiset22.3TheStudyHistoryofMultiset3CHAPTER3CLASSICALALGORITHM53.1JohnsonandTrotterAlgorithm53.2Ives'sIterativeAlgorithm73.3MultisetPermutationAlgor
