trying to find the permutation of a word

This is a discussion on trying to find the permutation of a word within the C Programming forums, part of the General Programming Boards category; this is the code i have and it crashes, cant figure out why, please help Code: char * flip(char* str, ...

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    25

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

  2. #2
    Ultraviolence Connoisseur
    Join Date
    Mar 2004
    Posts
    467
    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?

  3. #3
    Registered User
    Join Date
    Jan 2013
    Posts
    25
    the const code doesnt even compile

  4. #4
    Registered User
    Join Date
    Jan 2013
    Posts
    25
    and the last one doesnt work either, crashes

  5. #5
    Ultraviolence Connoisseur
    Join Date
    Mar 2004
    Posts
    467
    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).

  6. #6
    Registered User
    Join Date
    Jan 2013
    Posts
    25
    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;
    }

  7. #7
    Registered User
    Join Date
    Jan 2013
    Posts
    25
    i fixed it by changing
    Code:
    recursive(str, k++):
    to
    Code:
    k++;
    recursive(str, k);
    and now it only will print cat

  8. #8
    Registered User
    Join Date
    Sep 2011
    Location
    Dongargarh, India
    Posts
    16
    Quote Originally Posted by Clayton Cuteri View Post
    and now it only will print cat
    so, did you achieve your goal or do you want the program to do anything more???

  9. #9
    Registered User
    Join Date
    Jan 2013
    Posts
    25
    no i was trying to get all permutations of cat...

  10. #10
    Ultraviolence Connoisseur
    Join Date
    Mar 2004
    Posts
    467
    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.

  11. #11
    Registered User
    Join Date
    Jan 2013
    Posts
    25
    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

  12. #12
    Ultraviolence Connoisseur
    Join Date
    Mar 2004
    Posts
    467
    Quote Originally Posted by Clayton Cuteri View Post
    i fixed it by changing
    Code:
    recursive(str, k++):
    to
    Code:
    k++;
    recursive(str, k);
    and now it only will print cat
    Actually what you need to have is this:
    Code:
    recursive(str, ++k);
    That allows the recursive algorithm to "progress". Of course it still doesn't actually print the permutations because your flip logic is wrong and you only print the string 1 time at the end.

    EDIT: You need to increase k before your flip call...when you do that its getting a little closer to what you want...you also need to print the string more then once and the flip logic is still wrong even with that change.
    Last edited by nonpuz; 01-31-2013 at 08:53 PM.

  13. #13
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,303
    This seemed to work for me -> I'll let you figure out what is happening
    Code:
    recursive(str, (k+1));
    Fact - Beethoven wrote his first symphony in C

  14. #14
    Registered User
    Join Date
    Jan 2013
    Posts
    25
    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

  15. #15
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,303
    Use a debugger -> Step through your code and try to predict what should happen.
    Fact - Beethoven wrote his first symphony in C

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to find the longest word in text file?
    By alionas in forum C Programming
    Replies: 7
    Last Post: 03-07-2011, 12:05 PM
  2. C program to find inverses of a permutation
    By newbie123 in forum C Programming
    Replies: 6
    Last Post: 08-22-2010, 07:17 AM
  3. find word in a text file
    By 26friends26 in forum C++ Programming
    Replies: 7
    Last Post: 03-01-2010, 08:37 PM
  4. Word Find
    By malooch in forum C Programming
    Replies: 2
    Last Post: 11-28-2006, 10:11 AM
  5. Find a word in a 2d grid
    By The_Kingpin in forum C++ Programming
    Replies: 2
    Last Post: 02-24-2005, 04:38 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21