Java中的递归置换产生错误的结果 [英] Recursive permutation in Java generating wrong result
本文介绍了Java中的递归置换产生错误的结果的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
问题在于生成词典编排.
The problem is to generate lexicographic permutations.
起初,我的代码是这样的:
At first, my code was like this:
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));
结果变为正确.
这两种方式似乎与我相同.有人可以解释一下有什么不同以及为什么第一个会产生错误的结果.
This two ways seems equivalent to me. Can someone explain what's different and why the first one would generate wrong result.
谢谢
推荐答案
以下代码不断在for循环的每次迭代之间添加对prefix
的更改
The following one keep adding changes to the prefix
between each iteration in for-loop
prefix = prefix + numbers.charAt(i);
permutation(prefix,numbers.substring(0, i)+numbers.substring(i+1));
虽然此仅将对prefix
的更改传递给下一级调用,但它与该递归函数的目的很好地匹配
while this one only pass the changes on prefix
to the next level of invocation, it match the purpose of this recursive function well
permutation(prefix + numbers.charAt(i),numbers.substring(0, i)+numbers.substring(i+1));
要可视化每个级别下的递归调用:
To visualize the recursive call under each level:
(正确版本)
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中的递归置换产生错误的结果的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文