Thread: Having problems with a recursion problem

Hi friends,

I have this problem set that has to use recursion to permutate scores. I have read in all the numbers and have tested that it works but I am a little confused of how I need to keep going on. I attached the problem to this discussion and I could really use some help on this. I have also attached what I have so far.

Here is what I think I need to do:
I have to pass the structs into this permutation algorithm that is here:

Code:

#include <stdio.h>

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

int main() {
    
    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);
    
    // Print out the permutations.
    printf("\nHere are the permutations:\n\n");
    ListPermutations(word);
    
    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);
         
     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;
}

I don't know how to permutate this. Does anybody think they could give me a clue, not the answer, of course. I just need a little push. I need to permutate all possible combinations 3! which is:

Code:

Adam Diana   Adam Diana    Adam Ellen    Adam Ellen   Adam Fran   Adam Fran
Bob Ellen      Bob Fran         Bob Fran      Bob Diana    Bob Diana    Bob Fran
Carl Fran      Carl Ellen         Carl Diana    Carl Fran     Carl Fran     Carl Ellen

Here is my code so far:

Code:

#include <stdio.h>
#include <stdlib.h>

#define MAX_CHARS 20

// Structure that has 2 properties: name and scores.



struct person
{
    char *name;
    int *scores;
};

int main()
{
    // Opens the file and test to see if the file successfully opens.
    FILE *ifp = fopen("matching.txt", "r");
    if (!ifp)
    {
        printf("Unable to read file!\n");
        return -1;
    }

    // Variables: i is the initializer; num_pairs is the number of pairs; num_events is the number of speed dating events.
    int i, x, num_pairs, num_events;

    // These two lines read in the number of events and the number of pairs, respectively. TESTED AND READS NUMBER PROPERLY!!!

    fscanf(ifp, "%d", &num_events); // DONT FORGET!!!!!!!!!!!!!!
    for (x=0; x< num_events; x++)
    {
        fscanf(ifp, "%d", &num_pairs);

        // Declares the variable for men, of type struct person.
        struct person *men;
        men = malloc(num_pairs * sizeof(struct person));
        for (i=0; i< num_pairs; i++)
        {
            // This loop creates allocates memory for name and scores for each men.
            men[i].name = malloc(sizeof(char)*MAX_CHARS);
            men[i].scores = malloc(num_pairs * sizeof(int));
        }

        struct person *women;
        women = malloc(num_pairs * sizeof(struct person));
        for (i=0; i< num_pairs; i++)
        {
            // This loop creates allocates memory for name and scores for each women.
            women[i].name = malloc(sizeof(char) *MAX_CHARS);
            women[i].scores = malloc(num_pairs * sizeof(int));
        }

        for (i=0; i< num_pairs; i++)
        {
            fscanf(ifp, "%s ", men[i].name);
            printf("%s is getting scanned into men[%d].name!\n", men[i].name, i);
        }

        for (i=0; i< num_pairs; i++)
        {
            fscanf(ifp, "%s ", women[i].name);
            printf("%s is getting scanned into women[%d].name!\n", women[i].name, i);
        }

        for (i=0; i< num_pairs; i++)
        {
            int j;
            for (j=0; j<num_pairs; j++)
            {
                fscanf(ifp, "%d", &men[i].scores);
                printf("%s's score-- %d is getting scanned into men[%d].scores!\n", men[i].name, men[i].scores, i);
            }
        }

        for (i=0; i< num_pairs; i++)
        {
            int j;
            for (j=0; j<num_pairs; j++)
            {
                fscanf(ifp, "%d", &women[i].scores);
                printf("%s's score-- %d is getting scanned into women[%d].scores!\n", women[i].name, women[i].scores, i);
            }
        }

    }


    // Closes the file.
    fclose(ifp);
    return 0;
}