algorithm

子集树和排列树

宋正兵 on 2021-05-28

概念

假定有一个集合 S。

当我们要求解的结果是集合 S 的某一子集，那么对应的解空间是子集树，时间复杂度是 $O(2^{n})$。

当我们要求解的结果是集合 S 的元素的某一种排列的时候，其对应的解空间就是排列树，时间复杂度是 $O(n!)$。

算法描述

子集树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// t表示当前是树的第t层，即对集合S种的第t个元素进行判断
void backtrace(int t) {
    // 大于S中总的元素个数，遍历完成
    if (t > n) {
        output(x);
    }
    // 两种可能，加入或者不加入到解集合
    for (int i = 0; i <= 1; i++) {
        x[t] = i;
        // 满足约束条件，对t+1层进行判断
        if (constraint(t) && Bound(t)) {
            backtrace(t + 1);
        }
    }
}

排列树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// t表示集合S的第t个元素
void backtrace(int t) {
    if (t > n) {
        output(x);
    }
    // 第t个元素与其后面的所有元素进行交换位置
    for (int i = t; i <= n; i++) {
        swap(x[t], x[i]);
       	// 满足约束条件，对t+1层进行判断
        if (constraint(t) && Bound(t)) {
            backtrace(t + 1);
        }
        swap(x[t], x[i]);
    }
}

举例

排列树：JZ27 字符串的排列

题目大意：输入一个字符串,按字典序打印出该字符串中字符的所有排列。

思路：

按照排列树的算法描述来套进该问题，对于字符串中的第 t 个元素，依次和它之后的元素交换，可以得到不同的排列结果。然后做好去重即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
       ArrayList<String> resList = new ArrayList<>();
        if (str != null) {
            char[] arr = str.toCharArray();
            backtrace(arr, 0, resList);
            Collections.sort(resList);
        }
        return resList;
    }
    public void backtrace(char[] arr, int t, ArrayList<String> resList) {
        if (t >= arr.length) {
            String tempStr = String.copyValueOf(arr);
            if (!resList.contains(tempStr)) {
                resList.add(tempStr);
            }
            return;
        }
        for (int i = t; i < arr.length; i++) {
            swap(arr, t, i);
            backtrace(arr, t + 1, resList);
            swap(arr, t, i);
        }
    }
    public void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}



标签
algorithm