My String Permutations algorithm doesn't work

Question

I have written an algorithm for solving string permutations algorithm. It's having a problem, somewhere it's printing wrong output. I have walked through my code multiple times for different inputs, but I am unable to find what mistake I have done.

Would someone explain where I have made a mistake?

public static void main(String args[]) throws Exception {

    String str1 = "eat";
    int len = str1.length();
    char[] str = str1.toCharArray();
    recurPerm(str,0,len);
}
static void recurPerm(char[] str, int strstartind, int sz) {

    for(int i = strstartind; i < sz; i++){
        if(i > strstartind) {

            char temp = str[strstartind];
            str[strstartind] = str[i];
            str[i] = temp;

            recurPerm(str, strstartind + 1, sz);
        }
        else {
            recurPerm(str, strstartind + 1, sz);
        }
    }
    if(strstartind >= sz){
        System.out.println(str);
    }

    return;
}

Output

eat
eta
tea 
tae
eat
eta

But correct output is

eat eta aet ate tae tea

I tried debugging too. I found it too hard to debug because recursion being involved.

@NiVeR The output missing aet and ate.

Santhosh
– Santhosh

2018-07-24 10:50:27 +00:00
Commented Jul 24, 2018 at 10:50 — Santhosh
– Santhosh, Commented Jul 24, 2018 at 10:50

Instinct · Accepted Answer · 2018-07-24 11:41:37Z

3

You should restore the original state of the recursion, otherwise you keep mixing up the given parameters. The function parameter "strstartind" only indicates the right char to pick, if the original "str[]" is not changed, however you overwrite the original "str[]" at:

    str[strstartind] = str[i];
    str[i] = temp;

here is a working solution, that restores the recursion parameters:

public class DemoApplicationTests {

public static void main(String args[]) throws Exception {

    String str1 = "eat";
    int len = str1.length();
    char[] str = str1.toCharArray();
    recurPerm(str, 0, len);
}

static void recurPerm(char[] str, int strstartind, int sz) {

    for (int i = strstartind; i < sz; i++) {
        char temp = str[strstartind];
        str[strstartind] = str[i];
        str[i] = temp;
        recurPerm(str, strstartind + 1, sz);
        //restore state
        str[i] = str[strstartind];
        str[strstartind] = temp;
    }
    if (strstartind >= sz) {
        System.out.println(str);
    }

    return;
}
}

edited Jul 24, 2018 at 11:41

Instinct

3211 gold badge3 silver badges16 bronze badges

answered Jul 24, 2018 at 11:08

piradian

5348 silver badges20 bronze badges

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

6 Comments

Naseer Mohammad Over a year ago

thanxx. It works well.I understood your point, but Can you please explain what was mistake in my approach by taking example "eat" string where this not restoring approach being facing problem.

piradian Over a year ago

"Not restoring approach" was a general problem in your approach. It has nothing to do with the example you choose.

Naseer Mohammad Over a year ago

I am aware of it. But I am asking you take as example that "eat" string and explain where the problem has arised.

piradian Over a year ago

@Lukas-Franken edited my answer by adding additional description

Naseer Mohammad Over a year ago

@Lukas-Franken I am changing my original string. Thats fine but those are happening in different function calls. they shouldn't effect my functions local variable str right?? thats what i am asking

|

Collectives™ on Stack Overflow

My String Permutations algorithm doesn't work

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related