r-排列非递归生成算法及应用

《r-排列非递归生成算法及应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第34卷第4期宁夏大学学报(自然科学版)2013年12月Vo1．34No．4JournalofNingxiaUniversity(NaturalScienceEdition)Dec．2O13文章编号：0253—2328(2013)04—0301—05r一排列非递归生成算法及应用孙国伟，买阿丽(运城学院应用数学系，山西运城044O00)摘要：提出一种利用回溯法生成r一排列的算法．该算法使用栈和队列，并引入标记已选元素的方法，避免了回溯时的重复选择．生成的r一排列具有分组和对称性，且符合字典序．此算法也能生成全排列．利用该算法提出了r一组合

2、生成算法，分析了它们的时间和空间复杂度，并介绍了r一排列和r一组合算法在任务安排问题中的应用．关键词：排列；r_组合；栈；队列；非递归算法；回溯法；任务安排问题分类号：(中图)029；TP301．6文献标志码：A排列生成具有悠久的历史，在组合数学、计算对r一排列并不成立，因此对于r<时的排列生成并机图形学、群论、概率统计和计算机科学等领域应用不能直接适用．R．ABrualdi介绍了字典序生成r一广泛口]．从个不同元素中取出r(r≤n)个元素，组合的方法，并采用这种方法及全排列生成算法给并考虑元素的顺序，称为一个r一排列，当r一时称出一种

3、r一排列生成算法_2．Matlab提供了全排列为全排列．称生成个元素的所有P个r一排列为r一生成函数perms和r一组合生成函数combntnsl1，也排列生成[2]．相应地，若不考虑元素顺序，称为一个没有r一排列生成函数，可以首先利用combntns生成r一组合，称生成n个元素的所有c个r～组合为r一组C个r一组合，再调用C：次perms生成P：个r一排列．合生成引．将r一排列生成分为2个步骤进行，使得生成r一排列排列生成可以追溯到17世纪5O年代[3]．计算具有较高的时间和空间复杂度．同时，正如R．机发明后产生了许多利用计算机生成排

4、列的算法．Sedgewick和D．E．Knuth所提到的，随着的增大，D．H．Lehmer和R．J．Or&Smith分别对此问题进排列生成会遇到“组合爆炸”问题l1]，如17个整数行了总结[3]．R．Sedgewick于1977年对发表的算的全排列共有355687428096000个．法进行了系统的总结，并分析了不同算法的执行效对于任务安排问题_1卜]、N皇后l_1。及幻方率．2012年D．E．Knuth再次对此问题进行了系统构造r]胡等许多问题，其解虽然可以表示为排列，但阐述j．目前使用较多也比较著名的算法有基于交不是所有排列都是问题

5、的解，因此通常不需要在获换的递归算法、邻位互换法、因子计数法、字典序数得所有排列后，再在其中寻找问题的解．好的解决办法、递增进位制、递减进位制、Johnsor—Trotter算法法需要在生成排列的过程中舍去不可能的解，即进等[1]．它们的执行策略不同，时间和空间复杂度行剪枝．如文献[17]在生成全排列时利用棋盘对称各不相同，分别被应用在不同的问题中．Y．Bassil于性提高了N皇后问题的计算效率；文献[18]采用程2012年对比了3种算法在具体执行时分别采用蛮序验证算法，在利用字典序生成全排列时进行跳跃力法和分治法的执行效率_9]．除了

6、考虑生成给定集查找，将幻方的构造复杂度降低为o(n!)．因现有的合的全部排列，学者们也提出了一些算法生成一个全排列和r排列生成方法在生成后面的排列时均直随机排列[1]．另外，与以上这些顺序算法不同，L．接利用前面的排列，因此在生成过程中并不能很好Alonso等提出了一种并行算法，该算法也能够生成地进行剪枝或跳跃查找．文献[19]综合论述了组合随机排列．最优化理论与计算复杂性理论，指出组合优化在生已发表的排列生成算法大多是针对全排列生命科学和生物工程中的应用前景，如基因组的排序、成，且均是基于全排列的一些规律设计的，这些规律进化树的构建、

7、蛋白质结构的测定等，表明进行组合收稿日期：2013～02—26基金项目：国家自然科学基金资助项目(11071283，11241005)；生物数学重点实验室开放课题(SWSX201305)；运城学院科研基金资助项目(FZ-2012005)作者简介：孙国伟(198O一)，男，讲师，硕士，主要从事算法设计与分析、数学建模及应用研究，(电子信箱)sunkanry@163．corn．3O2宁夏大学学报(自然科学版)第34卷优化算法研究有非常重要的意义．Step4．3．4：本文提出一种生成r}列的非递归算法．之后Step4．3．1L3的队头出队；在

8、此算法基础上，提出生成r一组合的算法．分析了Step4．3．2将队头中数字域中的值压入栈S2；其时间和空间复杂度，并与已发表算法进行了对比Step4．3．3从S2的栈底开始，从下往上依次实验．最后介绍了2个