Thread: trying to find the permutation of a word

this is the code i have and it crashes, cant figure out why, please help

Code:

char * flip(char* str, int first, int second){
    char temp = str[first];
    str[first] = str[second];
    str[second] = temp;
    return str;
}


void recursive(char* str, int k){
    int i;
    if (strlen(str) == k)
        printf("%s", str);
    else{
        for (i = k; i < strlen(str); i++){
            str = flip(str, k, i);
            recursive(str, k++);
            str = flip(str, i, k);
        }
    }
}
int main(){
    char* cat = "cat";
    recursive(cat, 0);
    return 0;
}

Define your string here:

Code:

   char* cat = "cat";

Like this:

Code:

   const char * cat = "cat";

Then compile it. Do you get any warnings?

Now change it to this:

Code:

 char cat[] = "cat";

Now your code works! (or at least doesn't crash)...can you figure out whats going on here?

the const code doesnt even compile

and the last one doesnt work either, crashes

Ok, well the point is you are trying to modify a STRING LITERAL. In C you can not modify a string when it is declared like this:

char * s = "string";

You can only modify a string that has been allocated, or on the stack( ie a static array, as I showed above).

If it's still crashing after changing your declaration to 'char cat[] = "cat";' then you also have ANOTHER bug somewhere (fix this bug and repost and then I'll consider trying to help you find the second bug).

Code:

char* flip(char* str, int first, int second){
    char temp = str[first];
    str[first] = str[second];
    str[second] = temp;
    return str;
}


void recursive(char* str, int k){
    int i;
    if (strlen(str) == k)
        printf("%s", str);
    else{
        for (i = k; i < strlen(str); i++){
            str = flip(str, k, i);
            recursive(str, k++);
            //the program never reaches here
            //im assuming theres an issue with
            //it never popping the stack off
            str = flip(str, i, k);
        }
    }
}
int main(){
    char cat[] = "cat";
    recursive(cat, 0);
    return 0;
}

i fixed it by changing

Code:

recursive(str, k++):

to

Code:

k++;
recursive(str, k);

and now it only will print cat

Originally Posted by Clayton Cuteri

and now it only will print cat

so, did you achieve your goal or do you want the program to do anything more???

no i was trying to get all permutations of cat...

Yeah there seems to be a number of problems....you are running out the stack because the recursion never progresses, so eventually it simply segfaults because it can't locate the address of the flip() function anymore.

When I run your code in gdb, I get this:
#1 0x000000000040064e in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:17
#2 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#3 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#4 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#5 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#6 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#7 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#8 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#9 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#10 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#12 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#13 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#14 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#15 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#16 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#17 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#18 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#19 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#20 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#21 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
...
#11424 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11425 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11426 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11427 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11428 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11429 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11430 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11431 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11432 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11433 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11434 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11435 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11436 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
#11437 0x0000000000400663 in recursive (str=0x7fffffffdea0 "cat", k=0) at input.c:18
---Type <return> to continue, or q <return> to quit---
(note it still goes on, i got sick of hitting ENTER at this point to scroll further)

So notice how k never changes? Nor does the string.

in the new code i posted above i got k to increase, however flip is not wanting to flip the letters, trying to figure it out but no luck so far

i have narrowed it down to it having something to do with str[first] and str[second] being assigned. i have never been more confused about simpler code