Рекурсивная перестановка в 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)); 

к:

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

Результат будет правильным.

Этот два способа кажется мне эквивалентным. Может кто-нибудь объяснить, что изменилось, и почему первый из них породил бы неправильный результат.

Благодаря

Answer 1

следующие один продолжать добавлять изменения в 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 

Answer 2

Проблемы заключается в том, что, когда рекурсия происходит, когда значения из стека, когда вы делаете:

prefix = prefix + numbers.charAt(i); 

изменение будет происходить на каждом уровне иерархии вызовов. Но когда вы делаете:

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

Вы только выполняя prefix + numbers.charAt(i) один раз.