Return 递归给定列表的所有排列

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);
    }
}

（仅供参考：算法取自 this 答案）

我想修改算法，使其 returns 成为所有解决方案的列表而不是打印它们，例如：

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

您需要将 List 的副本添加到结果中，而不是每次都添加相同的副本。

改变

arrs.add(arr);

到

arrs.add(new ArrayList<>(arr));

完整方法：

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(new ArrayList<>(arr));
    }
    return arrs;
}

Demo

Answer 2

正如 Unmitigated 所指出的，您需要添加置换列表的副本。

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

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);
}

Return 递归给定列表的所有排列

Return all permutations of a given list recursively

java

algorithm

recursion

permutation