Recursive permutation in Java generating wrong result

Question

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

}
}

The result:

When I changed this two lines from

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

The result becomes right.

This two ways seems equivalent to me. Can someone explain what's different and why the first one would generate wrong result.

Thanks

Paul Lo · Accepted Answer · 2014-12-28 12:36:11Z

3

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

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:

(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

edited Dec 28, 2014 at 12:36

answered Dec 28, 2014 at 12:22

Paul Lo

6,1466 gold badges33 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

noyoudont Over a year ago

Thanks, so the value passed is indeed the same, but I forgot I was using the value of prefix in the for-loop.

Paul Lo Over a year ago

@AntonZ ya, hope the updated table looks clear to you for why the error result looks like that.

Maroun · Accepted Answer · 2014-12-28 12:21:22Z

1

The problem is that when the recursion occur, when the values are popped from the stack, when you do:

prefix = prefix + numbers.charAt(i);

The changes will occur on each level of the call hierarchy. But when you do:

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

You're only performing prefix + numbers.charAt(i) once.

edited Dec 28, 2014 at 12:21

answered Dec 28, 2014 at 12:14

Maroun

96.3k30 gold badges195 silver badges249 bronze badges

Collectives™ on Stack Overflow

Recursive permutation in Java generating wrong result

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related