recursive permutations

This is a discussion on recursive permutations within the C Programming forums, part of the General Programming Boards category; I have the code to produce all permutations of a character string. the code is as follows: Code: void RecursivePermute(char ...

  1. #1
    Registered User
    Join Date
    May 2008
    Posts
    11

    recursive permutations

    I have the code to produce all permutations of a character string.

    the code is as follows:

    Code:
    void RecursivePermute(char str[], int k) {
         
         int j;
         // Base-case: Since all letters are fixed, we can ONLY print
         // what's stored in str.
         if (k == strlen(str))
         {
             printf("\nBase case: %s\n", str);
         }    
         else {
              
             // Loop through each possible starting letter for index k,
             // the first index for which we have a choice.
             for (j=k; j<strlen(str); j++) {
             
                 // Place the character stored in index j in location k.
               
                     ExchangeCharacters(str, k, j);
                 
                 // Print out all of the permutations with that character
                 // just chosen above fixed. 
     
                     RecursivePermute(str, k+1);
     
    
                 // Put the original character that used to be there back
                 // in its place.
                      ExchangeCharacters(str, j, k);
             
                 
             }
         }
    }
    This only works if all of the letters in str are different. I don't even know where to begin to prevent "doubles" from printing out...any suggestions?

    Thanks

  2. #2
    Registered User
    Join Date
    May 2008
    Posts
    53
    Perhaps you can check whether the two characters you're exchanging are really the same, and ignore this permutation set if they are?

    --
    Computer Programming: An Introduction for the Scientifically Inclined

  3. #3
    Registered User
    Join Date
    May 2008
    Posts
    11
    Thanks for the reply...I gave it a try, but there are still situations that doubles will print:

    example:

    word: DAD
    A will swap with both D's yielding the same word.

    Anyone have an idea?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I'm guessing what you'll need to do here is look at your for loop. You're currently putting every possible j into that k'th position that we're looking at. So what you need to check is, not necessarily that the letters you're exchanging are the same, but that if you put 'D' into position when j=7, you don't also put 'D' into position when j=11. If you keep a "used letter board" around, then you'll know whether to go ahead with the recursion or skip it.

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    Quote Originally Posted by wd_kendrick View Post
    Thanks for the reply...I gave it a try, but there are still situations that doubles will print:

    example:

    word: DAD
    A will swap with both D's yielding the same word.

    Anyone have an idea?
    Why do you think the duplicates are incorrect? Each of the two "D" letters is a unique object. They just happen to look the same.

  6. #6
    Registered User
    Join Date
    May 2008
    Posts
    11

    lol

    The broader program is a program that can decipher scrambled words from a dictionary file.

    If the word DDA were put in, the Word ADD would be "found" twice...not a big deal...I am more curious because I am stumped than anything else.

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    Quote Originally Posted by wd_kendrick View Post
    The broader program is a program that can decipher scrambled words from a dictionary file.

    If the word DDA were put in, the Word ADD would be "found" twice...not a big deal...I am more curious because I am stumped than anything else.
    Stumped about what?

    You can eliminate the duplicates, if you really want, by changing your algorithm to produce the permutations in lexical order. When in lexical order, all of the identical permutations will be adjacent to each other and are easily filtered.

    Slightly easier, just use your present algorithm and sort the results. This also puts them in lexical order and makes it trivial to filter out the duplicates.

  8. #8
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Yeah thats how I did it in the past.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 04:42 AM
  2. permutations of a string
    By agarwaga in forum C Programming
    Replies: 1
    Last Post: 05-23-2006, 08:52 AM
  3. difference between recursive and iterative
    By Micko in forum C Programming
    Replies: 33
    Last Post: 07-06-2004, 09:34 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM

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