Java中的递归排列生成错误结果

Question

问题是产生字典序排列。

起初，我的代码是这样的：

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));

to:

permutation(prefix + numbers.charAt(i),numbers.substring(0, i)+numbers.substring(i+1));

结果变得正确了。

这两种方式对我来说似乎是等价的。有人能解释一下它们的不同之处以及为什么第一种方式会生成错误的结果吗？

谢谢

- AntonZ

Answer 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

- Paul Lo

---

谢谢，所以传递的值确实是相同的，但我忘记在for循环中使用了“prefix”的值。 - AntonZ

@AntonZ ，希望你能明白为什么错误结果看起来如此清晰，更新后的表格。 - Paul Lo

Answer 2

问题在于递归发生时，当值从堆栈中弹出时，执行以下操作:

prefix = prefix + numbers.charAt(i);

这些变化将在每个调用层次上发生。但当您执行以下操作时：

permutation(prefix + numbers.charAt(i),numbers.substring(0, i)+numbers.substring(i+1));

您只执行了一次 prefix + numbers.charAt(i)。

- Maroun