我的任务是实现一个蛮力算法,以输出整数[1,2,...,n]对某个n的所有排列组合。然而,我似乎在向HashSet添加ArrayList对象时遇到了一些问题。
static Set<List<Integer>> allPermutations(int n){
if(n<=0){throw new IllegalArgumentException();}
List<Integer> thisPermutation = new ArrayList<Integer>();
for(int i=1; i<=n; i++){
thisPermutation.add(i);
}
Set<List<Integer>> allPermutations = new HashSet<List<Integer>>();
while(true){
allPermutations.add(thisPermutation);
thisPermutation = nextPermutation(thisPermutation);
if(thisPermutation == null){break;}
}
return allPermutations;
}
我发现连续调用 "nextPermutation "确实能找到所有的排列组合, 但我不明白当我把排列组合添加到HashSet "allPermutations "中会发生什么. 我在运行n=3的时候得到的输出是这样的。
[[3, 2, 1, 1, 2, 1, 1, 3, 1, 2], [3, 2, 1], [3, 2, 1, 1, 2, 1, 1], [3, 2, 1, 1], [3, 2, 1, 1, 2, 1, 1, 3, 1], [3, 2, 1, 1, 2, 1]]
我是Java新手,希望能得到帮助。
编辑:这是NextPermutation函数。
static List<Integer> nextPermutation(List<Integer> sequence){
int i = sequence.size() - 1;
while(sequence.get(i) < sequence.get(i-1)){
i -= 1;
if(i == 0){
return null;
}
}
int j = i;
while(j != sequence.size()-1 && sequence.get(j+1) > sequence.get(i-1)){
j += 1;
}
int tempVal = sequence.get(i-1);
sequence.set(i-1, sequence.get(j));
sequence.set(j, tempVal);
List<Integer> reversed = new ArrayList<Integer>();
for(int k = sequence.size()-1; k>=i; k--){
reversed.add(sequence.get(k));
}
List<Integer> next = sequence.subList(0, i);
next.addAll(reversed);
return next;
}
List<Integer> sequence
传递给 nextPermutation
方法,并在该方法内部进行修改。sequence.set(j, tempVal);
. 因此,每次修改原来的排列组合时,都会在方法: 。nextPermutation
方法被称为(呼叫分享).
然而,你可以很容易地修改你的代码,在方法中创建一个列表的副本。
static List<Integer> nextPermutation(final List<Integer> s) {
List<Integer> sequence = new ArrayList<>(s);
int i = sequence.size() - 1;
// ...
}