Recursive permutation in Java produces incorrect result
The problem is in creating 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));
}
}
}
}
Result:
123 1232 1213 12131 12312 123121
When I changed two lines from
prefix = prefix + numbers.charAt(i); permutation(prefix,numbers.substring(0, i)+numbers.substring(i+1));
in
permutation(prefix + numbers.charAt(i),numbers.substring(0, i)+numbers.substring(i+1));
The result becomes correct.
These two methods seem similar to me. Can someone please explain what is different and why the first one would produce the wrong result.
thank
source to share
The following adds changes to prefix
between each iteration in the for-loop
prefix = prefix + numbers.charAt(i); permutation(prefix,numbers.substring(0, i)+numbers.substring(i+1));
while this one only passes the changes to prefix
the next level of the call, it suits 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 below each level:
(Correct version)
Level: 1 | 2 | 3
-- | ---- | ---
prefix 1 | 12 | 123
| 13 | 132
2 | 21 | 213
| 23 | 231
3 | 31 | 312
| 32 | 321
(Wrong version)
Level: 1 | 2 | 3
--- | ------ | -----
prefix 1 | 12 | 123
| 123 | 1232
12 | 121 | 1213
| 1213 | 12131
123 | 1231 | 12312
| 12312 | 123121
source to share
The problem is that when the recursion happens when the values are popped off the stack, when you do:
prefix = prefix + numbers.charAt(i);
Changes will occur at each level of the call hierarchy. But when you do this:
permutation(prefix + numbers.charAt(i),numbers.substring(0, i)+numbers.substring(i+1));
You only execute prefix + numbers.charAt(i)
once.
source to share