# Thread: Having problems with a recursion problem

1. ## 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)
{
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;
}```

2. 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.