Java中的遞歸排列生成錯誤結果

起初，我的代碼是這樣的：

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

} 
}

結果：

當我改變了這兩條線從

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

結果變得正確。

這兩種方式似乎與我相當。有人可以解釋什麼是不同的，爲什麼第一個會產生錯誤的結果。

感謝

來源

2014-12-28 AntonZ

每次迭代之間在for循環

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

而這一個只傳遞prefix的更改調用的下一層以下一個不斷增加改變到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

來源

2014-12-28 12:22:40

感謝，所以傳遞的值確實是一樣的，但我忘了我是用在for循環prefix'的'值。 – AntonZ

@AntonZ ya，希望更新後的表格看起來很清楚爲什麼錯誤結果看起來像這樣。 –

可視化完全清除雲。謝謝！ – AntonZ

的問題是遞歸發生時，當值從堆棧，當你做彈出：

prefix = prefix + numbers.charAt(i);

的變化將在電話會議上每個層次發生。但是當你這樣做：

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

你只執行prefix + numbers.charAt(i)一次。

來源

2014-12-28 12:14:58 Maroun

Java中的遞歸排列生成錯誤結果

回答

相關問題