递归地返回给定列表的所有排列。

Question

下面的算法打印给定列表arr的所有排列

public class Permute {
    static void permute(java.util.List<Integer> arr, int k) {
        for (int i = k; i < arr.size(); i++) {
            java.util.Collections.swap(arr, i, k);
            permute(arr, k + 1);
            java.util.Collections.swap(arr, k, i);
        }
        if (k == arr.size() - 1) {
            System.out.println(java.util.Arrays.toString(arr.toArray()));
        }
    }

    public static void main(String[] args) {
        Permute.permute(java.util.Arrays.asList(1, 2, 3), 0);
    }
}

(FYI:该算法取自this答案)

我想修改该算法，以便它返回所有解决方案的列表，而不是打印它们，例如：

static List<List<Integer>> permute(java.util.List<Integer> arr, int k);

我该怎么做？我尝试了对算法进行以下修改，但没有奏效：

public class Permute {
    static List<List<Integer>> permute(java.util.List<Integer> arr, int k) {
        List<List<Integer>> arrs = new ArrayList<>();
        for (int i = k; i < arr.size(); i++) {
            java.util.Collections.swap(arr, i, k);
            arrs.addAll(permute(arr, k + 1));
            java.util.Collections.swap(arr, k, i);
        }
        if (k == arr.size() - 1) {
            arrs.add(arr);
            System.out.println(java.util.Arrays.toString(arr.toArray()));
        }
        return arrs;
    }

    public static void main(String[] args) {
        List<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 3));
        System.out.println(Permute.permute(arr, 0));
    }
}

代码编译并执行，但是给出了[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]的错误结果。我很难理解为什么代码不能工作，以及如何正确地执行它。任何帮助都是非常感谢的。

Answer 1

如前所述，您需要添加配置列表的副本。

此外，不需要创建一个新列表来保存递归的每个级别上的排列。您可以创建一个列表来保存结果并将其作为参数传递：

static void permute(List<List<Integer>> res, List<Integer> arr, int k) {
  if (k == arr.size() - 1) {
    res.add(new ArrayList<>(arr));
    return;
  }

  for (int i = k; i < arr.size(); i++) {
    Collections.swap(arr, i, k);
    permute(res, arr, k + 1);
    Collections.swap(arr, k, i);
  }
}

public static void main(String[] args) {
  List<List<Integer>> res = new ArrayList<>();
  permute(res, Arrays.asList(1, 2, 3), 0);
  System.out.println(res);
}