资源描述：
《多重集的全排列算法研究-毕业论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、厦门大学本科毕业论文多重集的全排列算法研究[摘要]字符串的全排列问题是一个非常有趣的数学问题并且有悠久的历史，本文提出了一种新的并且经过模拟证明是最快的全排列算法。对于一个长度为N的字符串来说，如果它有k个不同的字符，每个字符重复出现的次数分别为：,....,当这些数不全为1时,我们称其为输入有重复的多重集字符串,它们的全排列问题也因此被称为多重集字符串的全排列问题。若==....=，则每个字符出现的次数均为1，我们称其排列为输入无重复的单纯集全排列问题。对这两种不同的排列，历史上均出现过很多经典算法。如对于单纯集全排列，著名算法大师Sedgewick在其著作“permuta
2、tiongenerationmethods”[3]中指出，名为Heap[1]的算法是递归中最快的，而Ives[2]算法是迭代中最快的。对于多重集来说，Ruskey[8]、ConstantTime[4]算法是比较快的。在这些与之比较的算法中，本文将着重介绍经典的单纯集全排列算法Ives,JohnsonandTrotter和多重集全排列算法ConstantTime。与传统的全排列算法或者只产生多重集的全排列或者只产生单纯集的全排列不同，本文的算法对于输入无重复的单纯集以及输入有重复的多重集字符串均能快速产生正确的全排列。我们引入一个自然数数组：Mappings[]，将各个不同的输
3、入字符一对一映射到这个连续的自然数数组，排列过程中仅对这个自然数组进行操作，在适当的时机对数组元素换位，从而不断缩小子问题的取值空间，实现无需进行大量判断自动排除重复输出。最后排列的结果根据自然数与字符对应关系得到。通过对长度N=10,11,12,13,14,15,16,和17的输入进行模拟并且和其它11种经典的单纯集全排列算法和多重集全排列算法所用的时间加以比较[1][2][3][4][5][6][7][8][9][10]，本文的算法TWDRI是速度最快的，在占用内存方面也很有优势，平均内存不到800K。此外，我们还介绍了一种对于多重集输入的所有可能排列测试其平均排列时间的
4、算法。[关键词]多重集全排列全排列的产生最快字符串的全排列第43页共43页厦门大学本科毕业论文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
