问题是生成字典排列。
起初,我的代码是这样的:
public class Problem24 {
public static void main(String[] args) {
permutation("","123");
}
public static void permutation(String prefix, String numbers) {
if (numbers.length() == 0) {
System.out.println(prefix);
} else {
for (int i = 0; i < numbers.length(); i++) {
prefix = prefix + numbers.charAt(i);
permutation(prefix,numbers.substring(0, i)+numbers.substring(i+1));
}
}
}
}
结果:
123
1232
1213
12131
12312
123121
当我从
更改这两行时prefix = prefix + numbers.charAt(i);
permutation(prefix,numbers.substring(0, i)+numbers.substring(i+1));
到:
permutation(prefix + numbers.charAt(i),numbers.substring(0, i)+numbers.substring(i+1));
结果变成正确的。
这两种方式在我看来是等价的。有人可以解释有什么不同以及为什么第一个会产生错误的结果。
谢谢
最佳答案
下面的代码在 for 循环的每次迭代之间不断添加对 prefix
的更改
prefix = prefix + numbers.charAt(i);
permutation(prefix,numbers.substring(0, i)+numbers.substring(i+1));
虽然这个函数只是将 prefix
的变化传递给下一级调用,但它很好地符合这个递归函数的目的
permutation(prefix + numbers.charAt(i),numbers.substring(0, i)+numbers.substring(i+1));
可视化每个级别下的递归调用:
(正确的版本)
Level: 1 | 2 | 3
-- | ---- | ---
prefix 1 | 12 | 123
| 13 | 132
2 | 21 | 213
| 23 | 231
3 | 31 | 312
| 32 | 321
(错误的版本)
Level: 1 | 2 | 3
--- | ------ | -----
prefix 1 | 12 | 123
| 123 | 1232
12 | 121 | 1213
| 1213 | 12131
123 | 1231 | 12312
| 12312 | 123121
关于java - Java中的递归排列产生错误的结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27676267/