CODEWITHSUNDEEP
javastringalgorithmpermutation
Naseer Mohammad
Naseer Mohammad

Reputation: 431

My String Permutations algorithm doesn't work

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.

Upvotes: 2

Views: 103

Answers (1)

piradian
piradian

Reputation: 444

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

Upvotes: 4

Related Questions