多重集全排列算法研究开题报告.doc

厦门大学软件学院《毕业设计(论文)》开题报告
学生姓名

班级

学号

指导教师姓名
陈金柱
职称
教授
所在单位
厦门大学软件学院
毕业设计(论文)题目
多重集全排列算法研究
毕业设计(论文)的目标:
一、总体目标
字符串的全排列问题是一个经典的数学排列问题,它有着悠久的历史,也有着广泛的实际应用,比如说在密码学领域对输入的一些数字或字符产生其对应的密码;在生物医学领域DNA的全排列等等。因此研究字符串的全排列问题有很大的实际意义。此次毕业设计的目标是搜集当今世界上关于字符串全排列的各种算法,进而与Professor Ray的算法进行对比,包括内存,运行速度等各方面的性能分析对比,从而证明Professor Ray的新算法是目前世界上最高效的算法。
实现方法:
一、基本概念
全排列的定义
对给定的字符串进行排列组合,得到N种准确无重复无遗漏的排列结果,叫做字符串的全排列。主要有下面两种情况的全排列:
不重复字符串的全排列
给定的字符串不包含重复字母,将其进行全排列,把其所有可能的全排列准确无重复无遗漏地列举出来。例如:输入ABC,其全排列的结果有6种,分别为:ABC,ACB,BAC,BCA,CAB,CBA。
重复字符串的全排列
给定的字符串包含重复字母,将其进行全排列,把其所有可能的全排列准确无重复无遗漏地列举出来。例如:输入AAB,其全排列的结果有3种:分别为:AAB,ABA,BAA。
二、具体实现
这里主要根据不同阶段的具体情况,分别阐述具体的实现方法:
、收集资料
选定合适的关键字进行搜索,关键字包括:string permutation, permutation generation method, combination, algorithm。对搜索出的文章进行分类筛选,找出当今世界上最新的最好的全排列算法,仔细研读,为下一阶段的模拟比较作好准备。
搜索的著名数据库包括:
ACM(美国计算机学会) Digital Library
ACM(Association puting Machinery,美国计算机学会)数据库收录ACM全文期刊29种,会议录近170种,超过69,000篇的全文文章、1954年至今出版的期刊、杂志目录以及超过23,000 篇的引用文献、1985年至今出版的990多卷会议记录的文章目录以及超过48,000 篇的引用文献、与ACM文章关联的大约150万篇参考文献(其中20万篇参考文献链接有全部书目资料,5万篇可以链接全文)、ACM的“在线计算机文献指南”(可以查询和浏览来自计算机领域重点出版社的巨大书目资料库,包括图书、期刊、会议录和论文)。
SCI (《科学引文索引》Science Citation Index)
SCI是美国科学情报研究所(Institute for Scientific Information,简称ISI,网址:一部世界著名的期刊文献检索工具,其出版形式包括印刷版期刊和光盘版及联机数据库,现在还发行了互联网上Web版数据库(即Web of Science)。SCI收录全世界出版的数、理、化、农、林、医、生命科学、天文、地理、环境、材料、工程技术等自然科学各学科的核心期刊约3500种。ISI通过它严格的选刊标准