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

多重集的全排列算法研究暨分类
摘要
本文介绍一种新式的,经过优化了的多重集全排列算法TWDRI。同时,本文也分析了所有的多重集全排列算法并按照算法的实现机制进行了分类。为了公平起见,本文通过经验总结出一套模拟和比较算法的机制,并很好地应用在了TWDRI与其他同类算法的性能比较里面。值得庆幸的是,TWDRI确实能够为多重集的全排列和纯排列处理提供理想的速度。论文剩余的部分将研究格雷编码在多重集全排列领域中的应用。并总结了从格雷编码第一次被应用到此领域一直到现在的应用情况和评论,以及一些相关的问题,其中有些问题一直到现在还是处于未解决阶段。在最后,将展望一下多重集全排列算法的一些可能的发展前景,将从目前正在进行的甚至到未来可能的发展方向做个综述,希望以后可以为这个领域进行进一步的研究打下基础。
关键词 TWDRI 算法算法比较全排列格雷编码
Abstract
The thesis is going to introduce TWDRI, a new optimized permutation algorithm of multiset. At the same time, almost all the algorithms of permutation of multiset are analyzed and classified due to their inner principles. To be equitable, we employ methodology summarized from experience to simulate pare data of TWDRI to other well known/unknown algorithms in this field. We are pleased to see ideal speed in both pureset and multiset permutation processing. In the remainder of this thesis, we pay main attention to Gray code applied in the said field. We focus on its development progress status from when Gray code first introduced into this field to the newest application ments, and some open problems would be issued which have not been resolved until now. In the end, expect possible development prospect and summarize direction developing and future of permutation of multiset, with the hope of constructing basis for possible future further studies in this said field.
Key words TWDRI; multiset; pureset; permutation; Gray code; algorithm
目录
第一章绪论 1
1
排列历史 1
纯排列算法的历史 1
多重集的全排列算法的历史 2
排列中的格雷码 2
2
论文的组织结构 3
第二章已有的排列算法的分析总结和分类 4
4
7
第三章新式的高性能的排列算法——TWDRI 16
16
算法的时间复杂度分析 17
算法的应用和特点 18
第四章排列算法中的格雷码应用研究 20
20
21
第五章测试、模拟与比较 24
24
24
26
26
28
TWDRI算法和其它纯排列算法的时间和内存比较 29
TWDRI 算法与其它多重集排列算法的比较趋势分析 30
第六章总结与展望 32
致谢 36
参考文献 37
Contents
Chapter 1 Introduct