Thread: 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

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

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?

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.

Originally Posted by wd_kendrick

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.

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.

Originally Posted by wd_kendrick

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.

Yeah thats how I did it in the past.