java - 请问这四种方式都是全排列吗，排列输出的顺序也不一样，它们的思路都是怎样的呢，有什么区别吗？

Question

1、第一种

import java.util.Arrays;

public class Main {

    
    public static void main(String[] args) {
        int[] a = new int[] { 1, 2, 3, 4 };
        f(a, 0, a.length - 1);
    }

    public static void f(int[] a, int start, int end) {

        if (start >= end) {
            System.out.println(Arrays.toString(a));
            return;
        }

        for (int i = start; i <= end; i++) {
            int temp = a[start];
            a[start] = a[i];
            a[i] = temp;
            f(a, start + 1, end);
            temp = a[start];
            a[start] = a[i];
            a[i] = temp;
        }
    }
}

第二种

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] a = new int[4];
        boolean[] vis = new boolean[5];
        f(a, 0, vis);
    }

    public static void f(int[] a, int k, boolean[] vis) {

        if (k >= a.length) {
            System.out.println(Arrays.toString(a));
        }

        for (int i = 1; i <= a.length; i++) {
            if (!vis[i]) {
                a[k] = i;
                vis[i] = true;
                f(a, k + 1, vis);
                vis[i] = false;
            }
        }
    }
}

第三种

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] a = new int[4];
        boolean[] vis = new boolean[4];
        f(a, 1, vis);
    }

    public static void f(int[] a, int k, boolean[] vis) {

        if (k > a.length) {
            System.out.println(Arrays.toString(a));
            return;
        }

        for (int i = 0; i < a.length; i++) {
            if (!vis[i]) {
                a[i] = k;
                vis[i] = true;
                f(a, k + 1, vis);
                vis[i] = false;
            }

        }
    }
}

第四种

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] a = new int[4];
        f(a, 1);
    }

    public static void f(int[] a, int k) {

        if (k > a.length) {
            System.out.println(Arrays.toString(a));
            return;
        }

        for (int i = 0; i < a.length; i++) {
            if (a[i] == 0) {
                a[i] = k;
                f(a, k + 1);
                a[i] = 0;
            }

        }
    }
}

Answer 1

1. 除第一种是对数组的元素进行全排列, 其余的都是对数组边赋值边进行排列的, 所以后面三种其实说是对"数组进行全排列"这种说法并不对, 只不过是下标刚好是和数值一样了

2. 对全排列的基本思想都是一样的, 使用递归前保存原来的状态, 递归弹出后恢复.

3. 结果不一样是因为对a[i]的赋值不同, 第二种是a[i] = i, 三四种a[i] = k;

4. 第四种的相当于二三种的简化,vis的标记位与a数组合并了, 但是这样不能对{0, 1, 2}这种数组进行全排列了, 因为0相当于未访问意思了

5. 第一种的end完全可以不用传, 本质就是数组长度