Having problems with a recursion problem

This is a discussion on Having problems with a recursion problem within the C Programming forums, part of the General Programming Boards category; Hi friends, I have this problem set that has to use recursion to permutate scores. I have read in all ...

  1. #1
    Registered User
    Join Date
    Nov 2012
    Posts
    51

    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;
    }
    Attached Images Attached Images
    Last edited by C0__0D; 02-08-2013 at 01:33 PM.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,640
    In the original code, you are permuting a string -- basically an array of chars. In the new code, you want to permute an array of struct person. The code requires very little changing, the algorithm is exactly the same for both, you just need to change all the char/str stuff to struct person/array of struct person.

    Change everywhere:
    Code:
    char str[]
    // to
    struct person people[]
    You also need to change your ExchangeCharacters function. It will follow the same idea, of swapping the contents of people[i] and people[j].
    Code:
    ExchangePeople(struct person people[], int i, int j)
    The last part you need to change is the printing line, perhaps to something that prints a name and a score.

    Start with that, get it working for one list. Adding the second list should be relatively easy.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursion problem
    By chaklader in forum C Programming
    Replies: 6
    Last Post: 05-28-2010, 10:34 PM
  2. Recursion Problem I think
    By clearrtc in forum C Programming
    Replies: 4
    Last Post: 07-31-2006, 08:10 PM
  3. A Problem with recursion
    By Adamkromm in forum C++ Programming
    Replies: 4
    Last Post: 09-28-2005, 09:35 PM
  4. Problems: When recursion is best
    By zahid in forum C Programming
    Replies: 8
    Last Post: 01-08-2002, 01:15 AM
  5. recursion problem
    By dustinc in forum C++ Programming
    Replies: 1
    Last Post: 10-29-2001, 04:29 AM

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