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

多重集全排列算法研究
[摘要] 本文提出一种新的全排列产生算法——TWDRI。该算法能同时解决一般的无重复输入的单集(pure permutation)问题和输入有重复的多重集(multiset permutation)问题,而且适用于各种不同字符输入情况,具有通用性。与已有算法不同,本文的新算法首先根据输入字符的频率预排序,再将各个不同输入字符一对一映射到连续的自然数数组。排列过程中仅对该数组进行操作,在适当的时机对数组元素换位,从而不断缩小子问题的取值空间,无需进行大量判断就可以自动排除重复输出。最后排列的结果再根据自然数与字符对应关系得到。而且对于多重集,本文提出了一种新的评估多重集算法性能的方法——平均时间(average time of multiset permutations),对于长度为N的输入,由它产生的所有的NN种情况都进行测试。我们进行了大量的模拟,测试了从10位到17位的输入情况,与已知的算法进行了比较[1][2][3][4][5][6][7][8][9][10],本文提出的算法表现出优秀的性能,比已有算法使用更快的时间得到所有排列结果。
[关键词] 全排列多重集算法

A Research into Multiset Permutation Algorithm
[Abstract] We introduce a new permutation generation method——TWDRI. It can solve both problems the general non-duplicated input(pure permutation) and the duplicated input(multiset permutation).Besides, it can handle all kinds of different characters input. Compared with the existing algorithms, this new algorithm is based on the frequency of input characters. It sorts the characters first by their frequency then map them to a natural numbers array(Mapping[]) one-by-one. When generating the permutation, it just manipulates the array element rather than characters. During the process, we delete the array element in order to shrink the value-space of the sub-problem and reduce lots of estimation for avoiding repeated output. At last, we will get the results according the Mapping[] to transform the natural numbers to the initial characters that we input. For the multiset permutation, we also introduce a new method to estimate such algorithms, which is called Average Time of Multiset Permutation. We evaluate our permutation time and memory consumption by simulating strings from length N = 10 to 17, respectively. We calculate average multiset permutation time for all possible NN inputs with each fixed length N above. pare our results with the fastest known and/or well-known algorithms[1][2][3][4][5][6][7][8][9][10] in detail. And this algorithm shows great performance, it use less time than all the algorithm that we have me