全排列问题

全排列问题

问题定义：

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:

[[1,2,3], [1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

问题分析：

人脑建模过程（类似“走迷宫”，试一步走一步，当前的路走不通就返回上一个路口）：

  1. 先取原数组的第一个数，把它“固定”在一个temp数组的首位，比如：[1，num，num]
  2. 再取出原数组的第二个数，把它“固定”在temp数组的第二位，比如：[1，2，num]
  3. 再取出原数组的第三个数，把它“固定”在temp数组的第三位，比如：[1，2，3]

此时我们得到了第一个排列

接着我们会想，如果在第二步中，取出的是第三个数，也就是[1，3，num]，那么显然就有[1，3，2]

再接着我们又会往前想，如果我们在第一步取的是第二个数，然后进行后续的操作。同样的如果第一步是是第三个数呢？

由图可知，我们每次不重复地从arr中取出一个数进行“固定”，每一次的“固定”都会影响下一次的“固定”的选择。通俗地讲，就是高中学过的排列组合里面的排列，第一次可以有三种选择，第二次有两种选择，第三次只有一种选择。

问题解决：

话不多说，先上代码： 

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
32
33
import java.util.Arrays;

public class fullPermutation {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int[] temp = new int[arr.length];
        boolean isVisit[] = new boolean[arr.length];
        perm(arr, 0, temp, isVisit);
    }
/**
     * 
     * @param arr 需要进行全排列的数
     * @param index 指向“固定”的位置的指针，值为0时，指向第一个固定位置，也就是temp[0]
     * @param temp 临时数组，用于存放被“固定”的数
     * @param isVisit  用来标记该数是否已经被选择“固定”
     */
    public static void perm(int[] arr, int index, int[] temp, boolean[] isVisit) {
        if (index==arr.length) {//结束递归条件
            System.out.println(Arrays.toString(temp));
            return;
        }
  
        for (int i = 0; i < arr.length; i++) {//遍历数组的每个数
            if (!isVisit[i]) {//判断数是否被使用，如果未使用则继续后面的操作
                temp[index] = arr[i];//将该数插入temp数组
                isVisit[i]=true;//将该数标记为已使用
                perm(arr, index + 1, temp, isVisit);//开始递归，插入下一个数
                    isVisit[i] = false;//执行到这一步的时候，说明有一个排列已经打印出来了，这时从后往前将每个数重置为未访问使用
            }
        }
    }
}

  • 人脑在“固定”数时能避开选择重复数，但是计算机本身是不能避开的。那么如何解决这个问题呢？很简单，我们可以给每个数arr[i]“贴上”一个名叫isVisit[i]的布尔值。如果第一次选择到的数，isVisit[i]会被赋值为true，表示该数已被访问使用，再加上一个if（! isVisit[i]）判断，所以在下一次再选择到这个数的时候就会跳过选择【见line 24】

  • 我们可以通过一个index指针来指向“固定（插入）”的位置

  • 用一个temp数组来储存所有全排列的数

  • for循环遍历所有数组，如果当前数arr[i]对应的isVisit[i]=true，则跳过继续for循环，直到某个数对应的isVisit值为false，将其插入temp

  • 然后开始递归，再回溯，回溯的时候将末尾数的isVisit赋值为false

  • 当index等于temp数组长度时打印temp并return

问题结果：