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

vcudknz3  于 2021-08-20  发布在  Java
关注(0)|答案(2)|浏览(395)

下面的算法打印给定列表的所有排列 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]] . 我很难理解为什么代码不起作用以及如何正确执行。感谢您的帮助。

vql8enpb

vql8enpb1#

您需要添加一份 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;
}

演示

8wigbo56

8wigbo562#

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

相关问题