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

A Non-recursive Algorithm of Generating r-Permutation and Its Applications

提出一种利用回溯法生成r-排列的算法.该算法使用栈和队列,并引入标记已选元素的方法,避免了回溯时的重复选择.生成的r-排列具有分组和对称性,且符合字典序.此算法也能生成全排列.利用该算法提出了r-组合生成算法,分析了它们的时间和空间复杂度,并介绍了r-排列和r-组合算法在任务安排问题中的应用.

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.