递归全排列问题(两种方法 Java 实现)
递归全排列问题(Java 实现)
问题描述
生成 {1,2,…,n} 的所有 n! 个排列
算法
1. 固定位置放元素
算法思想
生成元素{2,3,…,n}的所有排列,并且将元素 1 放到每个排列的开头
生成元素{1,3,…,n}的所有排列,并将数字 2 放到每个排列的开头
重复这个过程,直到元素{2,3,…,n-1}的所有排列都产生,并将元素 n 放到每个排列的开头
Java 源代码
复制代码
时间复杂度 $T(n) = \begin{cases}θ(1) & n = 1 \nT(n - 1) + n & n > 1 \\end{cases}$
2. 固定元素找位置
算法思想
首先,我们把 n 放在的位置 P[1]上,并且用子数组 P[2..n]来产生前 n-1 个数的排列
接着,我们将 n 放在 P[2]上,并且用子数组 P[1]和 P[3..n]来产生前 n-1 个数的排列
然后,我们将 n 放在 P[3]上,并且用子数组 P[1..2]和 P[4..n]来产生前 n-1 个数的排列
重复上述过程直到我们将 n 放在 P[n]上,并且用子数组 P[1..n]来产生前 n-1 个数的排列
Java 源代码
复制代码
时间复杂度 $T(n) = \begin{cases}θ(1) & n = 1 \nT(n - 1) + n & n > 1 \\end{cases}$
版权声明: 本文为 InfoQ 作者【若尘】的原创文章。
原文链接:【http://xie.infoq.cn/article/f9bafd6f9e06473e71305a783】。文章转载请联系作者。
评论