时间戳

首页 > 解决方案 > 递归返回给定列表的所有排列

java - 递归返回给定列表的所有排列

问题描述

以下算法打印给定列表的所有排列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);
    }
}

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

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

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]]。我无法理解为什么代码不起作用以及如何正确执行。任何帮助表示赞赏。

标签： javaalgorithmrecursionpermutation

解决方案

您需要将 的副本添加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

推荐阅读