| r-排列非递归生成算法及应用 |
| |
| 引用本文： | 孙国伟,买阿丽. r-排列非递归生成算法及应用[J]. 宁夏大学学报(自然科学版), 2013, 0(4): 301-305 |
| |
| 作者姓名： | 孙国伟 买阿丽 |
| |
| 作者单位： | 运城学院应用数学系,山西运城044000 |
| |
| 基金项目： | 国家自然科学基金资助项目（11071283,11241005）;生物数学重点实验室开放课题（SWSX201305）;运城学院科研基金资助项目（FZ-2012005） |
| |
| 摘 要： | 提出一种利用回溯法生成r-排列的算法.该算法使用栈和队列,并引入标记已选元素的方法,避免了回溯时的重复选择.生成的r-排列具有分组和对称性,且符合字典序.此算法也能生成全排列.利用该算法提出了r-组合生成算法,分析了它们的时间和空间复杂度,并介绍了r-排列和r-组合算法在任务安排问题中的应用.
|
| 关 键 词： | r-排列 r-组合 栈 队列 非递归算法 回溯法 任务安排问题 |
A Non-recursive Algorithm of Generating r-Permutation and Its Applications |
| |
| Sun Guowei,Mai Ali. A Non-recursive Algorithm of Generating r-Permutation and Its Applications[J]. Journal of Ningxia University(Natural Science Edition), 2013, 0(4): 301-305 |
| |
| Authors: | Sun Guowei Mai Ali |
| |
| Affiliation: | 1.Department of Applied Mathematics, Yuncheng University, Yuncheng 044000, China;) |
| |
| Abstract: | An r-permutation generation algorithm by backtracking is proposed in this paper.The stack and queue are used,and selecting repeatedly is avoided by labeling the selected elements.All r-permutations are grouping and symmetrical,which are visited in lexicographic order.Moreover,full permutation is also generated.According to r-permutation generation algorithm,an r-combinations generation algorithm is introduced.Time complexity and space complexity of two algorithms are analyzed.And the algorithms are applied to the task allocation problem. |
| |
| Keywords: | r-permutation r-combination stack queue non-recursive algorithm backtracking the task allocation problem |
| 本文献已被 维普 等数据库收录！ |
|
