子集树和排列树

宋正兵 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;
}
}