Java中的递归置换产生错误的结果 [英] Recursive permutation in Java generating wrong result

问题描述

问题在于生成词典编排.

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屋！