下面的算法打印给定列表的所有排列 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]]
. 我很难理解为什么代码不起作用以及如何正确执行。感谢您的帮助。
2条答案
按热度按时间vql8enpb1#
您需要添加一份
List
而不是每次添加相同的结果。改变
到
完整方法:
演示
8wigbo562#
正如unmitigated所指出的,您需要添加置换列表的副本。
而且,不需要创建一个新的列表来保存每个递归级别的排列。您可以创建一个列表来保存结果并将其作为参数传递: