多重集的全排列算法研究毕业论文1.doc

多重集的全排列算法研究
[摘要] 字符串的全排列问题是一个非常有趣的数学问题并且有悠久的历史,本文提出了一种新的并且经过模拟证明是最快的全排列算法。对于一个长度为N的字符串来说,如果它有k个不同的字符,每个字符重复出现的次数分别为:,...., 当这些数不全为1时,我们称其为输入有重复的多重集字符串, 它们的全排列问题也因此被称为多重集字符串的全排列问题。若==....=,则每个字符出现的次数均为1,我们称其排列为输入无重复的单纯集全排列问题。
对这两种不同的排列,历史上均出现过很多经典算法。如对于单纯集全排列,著名算法大师Sedgewick 在其著作“permutation generation methods”[3]中指出,名为Heap[1]的算法是递归中最快的,而Ives[2]算法是迭代中最快的。对于多重集来说,Ruskey[8]、Constant Time[4] 算法是比较快的。在这些与之比较的算法中,本文将着重介绍经典的单纯集全排列算法Ives, Johnson and Trotter 和多重集全排列算法Constant Time。
与传统的全排列算法或者只产生多重集的全排列或者只产生单纯集的全排列不同,本文的算法对于输入无重复的单纯集以及输入有重复的多重集字符串均能快速产生正确的全排列。我们引入一个自然数数组:Mappings[],将各个不同的输入字符一对一映射到这个连续的自然数数组,排列过程中仅对这个自然数组进行操作,在适当的时机对数组元素换位,从而不断缩小子问题的取值空间,实现无需进行大量判断自动排除重复输出。最后排列的结果根据自然数与字符对应关系得到。
通过对长度N=10, 11, 12, 13, 14, 15, 16, 和17的输入进行模拟并且和其它11种经典的单纯集全排列算法和多重集全排列算法所用的时间加以比较[1][2][3][4][5][6][7][8][9][10],本文的算法TWDRI是速度最快的,在占用内存方面也很有优势,平均内存不到800K。
此外,我们还介绍了一种对于多重集输入的所有可能排列测试其平均排列时间的算法。
[关键词] 多重集全排列全排列的产生最快字符串的全排列
A Research into Multiset Permutation Algorithm
[Abstract] The permutation of a string is an interesting mathematical problem and has a long history. In this paper, I will introduce the TWDRI algorithm, a new algorithm which is different from others. Through our simulation parison with other eleven algorithms, we have proved that our algorithm is the fastest algorithm among them. Suppose a string whose length is N. If there are k different characters, each has count,…, respectively. If all these counts don’t equal to 1, we call the string “multiset string”, therefore their permutations are called “multiset permutations.” If = =…..=, then the count for each character is 1, we call their permutations “pure permutations.”
Many algorithms were introduced for these two kinds’ permutations. For the pure permutation, the famous algorithm scholar Sedgewick described in his book “permutation generation methods” that the Heap algorithm[1] was the fastest recursive exchange algorithm while Ives[2] was the fastest iterative exchange algorithm. For the multiset permuta