印刷排列

Question

下面是一个leetcode问题:给定一个由不同整数组成的数组num，返回所有可能的排列。你可以返回所有可能的排列。你可以按任何顺序返回答案。

下面是我为上述问题编写的代码。它给出了正确的输出：

import java.util.*;

public class Main {

    public static void printPerm(int[] arr, int[] perm, int n){
        if(arr.length == 0){
            System.out.println(Arrays.toString(perm));
            return;
        }
        for(int i=0; i<arr.length; i++){
            int num = arr[i];
            int[] newArr = new int[arr.length-1];
            for(int j=0, k=0; j<arr.length; j++){
                if(j != i){
                    newArr[k] = arr[j];
                    k++;
                }
            }
            if(arr.length == n){
                perm[0] = num;
            }
            else {
                int[] tempArr = new int[n];
                for(int j=0; j<perm.length; j++){
                    tempArr[j] = perm[j];
                }
                tempArr[n - arr.length] = num;
                for(int j=0; j<tempArr.length; j++){
                    perm[j] = tempArr[j];
                }
            }
            printPerm(newArr, perm, n);
        }
    }

    public static void main(String[] args){
        int[] arr = {1,2,3};
        int n = arr.length;
        int[] perm = new int[n];
        printPerm(arr, perm, n);
    }
}

我还没有做过高级主题，如链接列表或Arraylist。因此，根据这一点，你对任何可以改进的地方有什么建议？我很高兴听到你的反馈。

Answer 1

我还没有做过高级主题，如链接列表或Arraylist。

没关系，我们这里不需要他们。

这种递归算法基于从数组中选择每个数，然后递归地生成其余项的所有排列，对于这个任务来说是一个非常合理的算法。有不同的选择，但这很好。

然而，它是通过大量繁重的数组操作来实现的.如果曾经用它来枚举足够大的排列，那么这需要花费大量的代码，可能还要花费时间。通过使用一些实现技巧，您可以使用非常类似的算法(可能甚至是相同的算法，取决于您如何看待它)，而无需分配任何额外的数组。

关键思想不是使用两个单独的数组，而是逻辑上将一个现有数组划分为两个不同的区域：“固定”区域，在递归中元素不会被更深层次地更改(这对应于perm)，而其余区域是从其中“提取”元素的区域(这对应于arr)。最初，固定区域的长度为零，递归向下的每一步都会再修复一个元素，当整个数组固定时，就会产生一个置换。在从一个递归级别返回到前一个级别后，一个元素是“未固定的”，并恢复到其在剩余区域中的旧位置。

在“固定”区域中添加任意选定的元素似乎需要移动数组中的许多元素，但这并不是必要的:我们可以用所选的元素“以这种方式”交换任何元素(这将改变递归中仍待选择的元素的顺序，但这很好，它只是改变了生成排列的顺序，这是这个问题允许的)。可以通过再次执行相同的交换来将该元素还原回其旧位置(在递归调用返回之后)。

可以进行一些小的优化(当在循环中反复使用不同的第二个元素交换相同的第一个元素时，交换可以执行一些冗余的写操作，可以通过从循环的第一次迭代中剥离(可能更多)来避免用自身交换元素)，但我将把它们留到下一次。我想在这篇综述中提出的要点不是如何以最有效的方式来实现，而是在相同的基本算法中添加一个简单但强大的技巧可以节省大量的数组操作。

这些代码最终变得简单得多：(这段代码显示出与您可能在互联网上找到的一些现有解决方案有很大的相似之处)

public static void printPerm(int[] arr, int fixed) {
    if (fixed == arr.length) {
        System.out.println(Arrays.toString(arr));
        return;
    }
    for (int i = fixed; i < arr.length; i++){
        swap(arr, fixed, i);
        printPerm(arr, fixed + 1);
        swap(arr, fixed, i);
    }
}

static void swap(int[] array, int a, int b) {
    int t = array[a];
    array[a] = array[b];
    array[b] = t;
}