Xing's Techlog

全排列

Posted on Edited on In

求数组或字符串的全排列算法。

不包含重复元素的序列求全排列

我们将第一个元素看作一部分A，其余元素看作一部分B，让第一个元素和后面的某一个元素交换，然后求B的全排列，递归执行上面语句，知道第二部分的开始指针到达数组末尾，我就得到一个排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void permutation(int[] nums, int start) {
    if (start == nums.length - 1) {
        for (int i : nums) {
            //得到一个排列
            System.out.print(nums);
        }
    }
    for (int i = start; i < nums.length; i++) {
        swap(nums, i, start);
        permutation(nums, start + 1);
        swap(nums, i, start);
    }
}
private void swap(int[] nums, int a, int b) {
    int tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
}

包含重复元素的序列求全排列

推荐使用Set这种数据结构存储排列结果，可以完美解决排列重复的问题。

还有一种方案是：添加if语句判断该元素是否重复，如果重复则不交换，这种方法不保证能完全解决重复元素的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//放在Set中的数据类型必须实现Comparable接口的compareTo方法
Set<String> res = new TreeSet<>();
public void permutation2(int[] nums, int start) {
    if (start == nums.length - 1) {
        StringBuilder sb = new StringBuilder();
        for (int i : nums) {
            sb.append(i);
        }
        res.add(sb.toString());
    }
    for (int i = start; i < nums.length; i++) {
        //swap nums[i] nums[start]
        swap(nums, i, start);
        permutation2(nums, start + 1);
        //swap nums[i] nums[start]
        swap(nums, i, start);
    }
}
private void swap(int[] nums, int a, int b) {
    int tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
}