黑马程序员技术交流社区

标题: n个元素{r1,r2,…,rn}的全排列算法。 [打印本页]

作者: Silvester 时间: 2014-6-30 21:00
标题: n个元素{r1,r2,…,rn}的全排列算法。
本帖最后由 Silvester 于 2014-6-30 21:01 编辑

n个元素{r1,r2,…,rn}的全排列算法设计思想。

设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。
集合X中元素的全排列记为perm(X)。
(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。

R的全排列可归纳定义如下：
当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；
当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。

思想举例：
(a)    -->  perm (a)

(ab)    -->  (a) perm (b)
         --> (b) perm (a)

(abc)    --> (a) perm (b, c)
                                 --> (b, c)
                                             -->  (b) perm (c)
                                             -->  (c) perm (b)
         --> (b) perm (a, c)
                                 --> (a, c)
                                             -->  (a) perm (c)
                                             -->  (c) perm (a)

            --> (c) perm (a, b)
                                 --> (a, b)
                                             -->  (a) perm (b)
                                             -->  (b) perm (a)

...........................
...........................
依次类推：

代码实现：

public class Test {
public static void main(String[] s) {
// 定义字符串abcde，字符串越长运行效率越低，用5个测试
String str = "abcde" ;
//temp 为辅助空间共享变量
String temp = new String();
//调用方法求 abcde 的全排列，
perm(str, temp);
}
//递归求取字符串全排列的方法
public static void perm(String s1, String s2) {
//循环，依次截取{ri}
for (int i = 0; i < s1.length(); i++) {
//控制{ri}中不能包含已被截取的(R)中的元素
if (!(s2.contains(s1.substring(i, i + 1)))) {
//打印已经求出的perm(X)
System.out.println(s2 + s1.substring(i, i + 1));
//递归调用求全排列的方法依次求取剩下的perm(X)
perm(s1, s2 + s1.substring(i, i + 1));
}
}
}
}

复制代码

时间复杂度分析：
核心语句为System.out.println(s2 + s1.substring(i, i + 1));
假设初始数据规模为n（即字符串长度为n）
1.  假设初始数据规模为n ,if判断和递归调用语句执行频度为n!次；
2.  for循环为程序增加的语句频度后为n次循环；
3.  总的语句执行频度为： O（n * n!），时间复杂度为： T (n!)
[ 注：时间复杂度与总的语句执行频度程线性关系,即：T(n) = O(f(n)中增长的最快的项/该项系数) ]

空间复杂度分析：
不考虑调用方法时方法区申请分配的空间和递归操作栈的空间
字符串长度（n） + 辅助空间共享变量（n），空间复杂度为：S （2n）

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2