I am trying to store the permutations generated by the recursive permutation function so that I can use them in main; however, I cannot figure how to get them to store correctly. I.E. when I run this function with a string AB, inside the recursive AB and BA gets printed but in main AB and AB again get printed.

Any suggestions on how to resolve this would be appreciated.

Thanks

Drew

#include <stdio.h>

void ListPermutations(char str[]);
void RecursivePermute(char str[], int k);
void ExchangeCharacters(char str[], int i, int j);

char** numPerms;
int ii = 0;

int main() {

    int i = 0;

       numPerms = calloc(sizeof(char *), (2));
        for(i=0; i<2;i++)
            numPerms[i] = calloc(sizeof(char), 2);

    char word[20];

    // Let the user enter a word to permute.
    printf("Please enter a word you would like to permute.\n");
    scanf("%s", word);
    printf("\n");
    // Print out the permutations.
    ListPermutations(word);

    printf("This should be the same as above but it is not\n");

    for(i=0;i<2;i++)
        printf("%s\n",numPerms[i]);

    system("PAUSE");
    return 0;

}

// Pre-condition: str is a valid C String.
// Post-condition: All permutations of str (assuming all distinct
//                 characters) will be printed.
void ListPermutations(char str[]) {

     // Call the appropriate recursive function with the correct
     // parameters.
     RecursivePermute(str, 0);
}

// Pre-condition: str is a valid C String, and k is non-negative and
//                less than or equal to the length of str.
// Post-condition: All of the permutations of str with the first k
//                 characters fixed in their original positions are
//                 printed. Namely, if n is the length of str, then
//                 (n-k)! permutations are printed.
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("%s\n", str);
         numPerms[ii] = str;
         ii++;
}
     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);
         }
     }
}

// Pre-condition: str is a valid C String and i and j are valid indexes
//                to that string.
// Post-condition: The characters at index i and j will be swapped in
//                 str.
void ExchangeCharacters(char str[], int i, int j) {

    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
}

Recommended Answers

All 5 Replies

If I understand you correctly, the ListPermutations function seems to work as desired. Youpass it "AB" and it displays "AB" and "BA", and that is what it'ssupposed to do, correct?

I see the printf statement on line 27 saying that you expect the printout below to also print out "AB" and "BA", but it doesn't. However, it does not and you are not sure why, correct?

I'm confused why you think it would. I see nothing about the numPerms variable (by the way, consider renaming this to something more descriptive. It's a char** . I would not expect a char** to store a number and this variable does not) that has anything to do with permutations, so naturally it's not going to print them, so that's your answer to why it doesn't work. You do permutations with the "word" variable, but that has nothing to do with the numPerms variable.

If the question is how to put all permutations into a container that you can use in main, that's a different question. First off you would need to pass the function a container. presumably that container would be a vector of strings (C++ style strings, not char* elements.I suppose you could use char* but why would you want to?). You're going to need to actually STORE each permutation. Right now you have one, count 'em one, string that's passed to your function, so at most you can get one permutation filled in the function. PRINTING all the permutations and STORING all the permutations are two different things entirely. Right now you print, then change the string, which means the string always holds only the LAST string. That will work in a recursive functon. Taht's not going to work in a loop in main.

numPerms[ii] = str;

str is a pointer, that pointer holds the address of word from main(). After RecursivePermute() runs to completion, every pointer in numPerms points to the same address.

Given that you've already allocated memory to each element in main(), you can fix both the problem and the obvious memory leak by copying the contents of str instead of assigning pointers:

strcpy(numPerms[ii], str);

One line changed, problem solved. :) There are other issues with the code, but I won't confuse things by pointing them out.

Wow, thats an insanely easy fix that took me way to long to figure out. Thanks for the insight

Appreciated!

Whoops. Missed the fact that numPerms was global. Sorry for the bad advice.

Double whoops. I also missed the fact that this is the C forum, not the C++ forum! Sorry again!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.