java实现全排列

我们设数字是 {1 2 3 4 5......n}，那么递归求全排列的思路是：

让第一个数不同，得到 n 个数列。其办法是：把第 1 个和后面每个数交换。

1 2 3 4 5......n2 1 3 4 5......n.....n 2 3 4 5......1

以上 n 个数列，只要第一个数不同，不管后面 n−1 个数是怎么排列的，这 n​ 个数列都不同。 这是递归的第一层。

继续：在上面的每个数列中，去掉第一个数，对后面的 n−1​ 个数进行类似的排列。例如从上面第 2 行的{2 1 3 4 5......n}进入第二层（去掉首位 2）：

1 3 4 5......n3 1 4 5......n......n 3 4 5......1

以上 n-1 个数列，只要第一个数不同，不管后面 n−2 个数是怎么排列的，这 n−1 个数列都不同。

这是递归的第二层。

重复以上步骤，直到用完所有数字。

以下是代码实现:

import java.util.Arrays;

public class Main{
    static int[] sequences = {1,2,3,4};//待全排序的序列
	
    public static void main(String[] args) {
        dfs(0,sequences.length-1);
    }

    public static void dfs(int start,int end) {
    	//递归结束条件
        if(start == end){
            System.out.println(Arrays.toString(sequences));//输出一个全排列序列
            return;
        }
        for(int i = start;i<=end;i++){
            swap(sequences, start, i);//把当前第1个数与后面所有数交换位置，注意所以i是从start开始
            dfs(start+1, end);
            swap(sequences, start, i);//恢复，用于下一次交换
        }
    }

    public static void swap(int[] a,int i,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}