Recursion Help

So, I'm going to apologize for asking for homework help again. Seems i do this far too often. I have a CS1 assignment on recursion and I am having a bit of a hard time. The purpose of the assignment is to take in data on how much certain couples liked each other during a speed dating session and come up with the best match overall. I put the data in a 2d array, with how well each couple gets along in it. The problem now is i am supposed to use recursion to come up with all the permutations, and add the number corresponding to how well each couple has match. There will always be same number of men as women, so thats easy enough. I think i'm just drawing a blank on the whole function. I looked at some other similar recursions(sample programs and the like) but all of them just did it with strings/1d arrays and I just cant really wrap my head around getting it to work for a 2d array.

Okay. Suppose you have some arbitrary pairing of men. Now suppose you sort the men in some particular order (say alphabetical; it doesn't matter). There will be only one way to permute the women so that their order matches up with the men, do you agree? Such that the first man is paired with the first woman, and so on down the line.

So if you fix the order of the men constant and just recurse through all possible permutations of women, you will have looped through all possible pairings of all the men and women.

Does that make sense?

Yes, that makes sense. That was along the lines of one of the things i was thinking of, but i just cant seem to figure out the phrasing of it. Should i do something like a loop for each of the men and calls the recursive function of the pairings with women? How should I go about adding the "likeability" ratings together to get a group total, should I start a new array of size n! and just add to it. Man the more programming classes I take the more convoluted it becomes. I really think i just need to take time off school and just teach myself this stuff, so that I at least have a general grasp of the concepts before attempting to do this.

Post the assignment.

You don't need an array of size n!.

Define a table, like[x][y], as the likeability of woman x with man y, for x and y in [1..n]. Then make a list L = [1..n] representing the men, and recurse through all possible permutations of L. Each permutation P represents a pairing, where woman k is paired with man P[k].

One possible permutation algorithm is described here: http://www.bearcave.com/random_hacks/permute.html
Personally I think the second one is the simplest to understand. Essentially you call the recursive function with a sequence and a starting number "start". The subsequence consisting of the first "start" items constitute the part of the permutation that is already built. Then it loops through all the remaining permutations by calling itself once for each remaining item as the next item in the subsequence.

Instead of printing the output at the last level of recursion, call a function that loops through the permutation and sums the likeability of each pairing. Since woman k is paired with man P[k], this is the sum of like[k][P[k]] for all k in [1..n].

I came up with a way that's a lot more simple, but it runs in O(n^n) time. With a few optimizations, you could get it to run in O(log n^n) time, but the amount of iterations you'd need is unreal. Russt's would run far faster, but it is more complicated.

This should define it enough for you. I thought this up while thinking about databases - many men, many women, many likes. How would that be stored in a database? A junction table, of course!

Code:

struct Compatibility
{
  int manID;
  int womanID;
  int manLike;
  int womanLike;
  struct Compatibility *next;
}

Jonathan has noticed that there are many match-making websites and event planners out there, but none of them seem to have very much success, on average. He is confident that he has an idea that is sure to beat all the others out there. Most of the websites out there ask clients all sorts of information and then produce a match score between pairs of people based on the answers to these questions. From there, anyone is free to email anyone else and can view the corresponding match score.
Of course, without meeting someone, you can never really predict if you might like them. Thus, Jonathan has decided that if he is to make a match-making business, he must get people to meet in person. An example of such an event is speed-dating, where each of the participants has several mini-dates. At the end of the night, participants go to a website and for each person they met, they simply state whether or not they are interested in that person. If there is a “match”, each person receives the other’s contact information. We may assume that any speed-dating session has an identical number of men and women.
What’s particularly troubling to Jonathan about the speed-dating scenarios is that some people may get many matches while others get none. This does not appeal to his egalitarian principles. He would prefer that after a round of speed-dating, each person gets matched with exactly one person of the opposite sex. Since Jonathan is a numbers guy, he would prefer that each person rate each person they have a mini-date with using a number from 1-10, represent how much they like that person. Using this data, Jonathan is sure he can match everyone up in a way that maximizes the total group’s “likeability” quotient.
A matching is simply a listing of each female in the group paired with an individual male.
The “likeability” quotient of a matching is as follows:
For each couple in the matching, look at how much the man likes the woman and the woman likes the man. (Both of these will be numbers from 1 to 10.) Record the minimum of the two numbers.
Add each of these numbers for each couple in the matching to determine the likeability quotient of the matching.
Since Jonathan is too busy heading the marketing division of the company, he has asked you to write the software that will calculate the matching that leads to a group’s maximum “likeability” quotient. Each group will be relatively small (no more than 10 men and 10 women). Thus, you can try all possible matchings (no more than 10!) and determine the one that leads to the greatest “likeability” quotient.
If more than one matching leads to the same maximal “likeability” quotient, your goal will be to minimize the difference in likeability between all of the pairs. Just go through each couple in the matching and add up the differences in how much they like each other. (If his score for her is 5 and her score for him is 2, then the difference is 3.) In case of ties, the matching you want to pick is the one that minimizes this sum.
The reasoning behind these metrics is fairly clear:
If one person likes the other person more, then as a pair, their liking for each other is only as strong as the person who likes the other person less.
Secondly, it’s generally bad to have a relationship where one person likes the other much, much more, since it creates an inequality. Thus, minimizing this inequality ought to be a way to break ties between competitive matchings.

You will read in input from a file, "input.txt". The name MUST BE “input.txt”. Have this AUTOMATED. Do not ask the user to enter “input.txt”. You should read in this automatically. (This will expedite the grading process.)
The first line of the file will contain a single positive integer, n, representing the number of speed-dating events. Each of the n test cases will follow. The first line of each test case will contain a single positive integer, c (1 < c < 11), representing the number of couples in the test case. The second line of each test case will contain c alphabetic strings (19 or fewer characters) separated by spaces representing the names of the men, from man #0 to man #(c-1). The third line of each test case will contain c alphabetic strings (19 or fewer characters) separated by spaces representing the names of the women, from woman #0 to woman #(c-1). The next c lines will contain the men’s ratings of the women. The first line will contain the ratings of man #0, the second line, the ratings of man #1, etc. Each of these ratings will be positive integers from 1 to 10, inclusive, separated by spaces. The first rating on each of these lines is for woman #0, the second rating is for woman #1, etc. the last c lines of each test case will contain the women’s ratings of the men, with the first line being woman #0’s ratings, the second line being woman #1’s ratings, etc. Similarly, on each of these lines, the first integer will be the rating of man #0, the second integer will be the rating of man #1, etc, and all of these ratings will be separated by spaces as well.
Output Format
***NOTE***: You should generate your output to a FILE that you will call “out.txt”.
For each test case, output the following header:
Matching #k: Maximum Score = X.
where k (1 ≤ k ≤ n) represents the speed dating session, and X represents the maximum “likeability” quotient for the group.
Skip a blank line, and follow with each pair in the matching, the man’s name followed by the woman’s name, separated by a space. The ordering of the matching should be in the same ordering the men were given in the input file.
After each test case, skip two blank lines.

Your program MUST use recursion. SPECIFICALLY, your program MUST use the recursive PERMUTATION algorithm that we discussed in class. You will use this to get all the different permutations of matches. That is the purpose of this assignment. You will get no more than 50% of the grade if you do not use recursion for the main part of the program.

The way I'm thinking of it should take O(n!) time and O(n^2) space, where the recursive step looks something like

Code:

LinkedList recurse(array subset) {
  pointer a = array(length of subset)
  int v = array(length of subset)
  for (each element e in subset) {
    a[e] = recurse(subset without e)
    v[e] = value(a[e])
  }
  i <- index of max(v)
  create new LL element containing element i, pointing at a[i]
  return this new LL of e[i] -> a[i]
}

value(LinkedList in) {
  if (in.next is null)
    return 0;
  else
    return in.value + value(in.next);
}

At its worst, you'll have n linkedlists of length n-1 (at the head of the recursion) taking O(n^2) space... and of course, doing permutations this way means n! different ways.

At the end you end up with returning a linkedlist containing the best value arrangement.

Your linkedlistelements would have to be pointing at an object containing:
- woman
- pairing value
plus it might be useful to have
- man
- total value of the list below this element
Which would increase storage size, but make the class's operations faster & more intuitive.


If you did include total value then the value function would be just a[i].value.getTotal() or something instead, and when you created the new LLE you'd add next.value + next.total...

talked to a teachers assistant, got the permutation done, trying to get the same function to get the best value for the various permutations.

Code:

void RecursivePermute(int *str, int k, int len, int **weakLink, int bestScore) {
    
     int j, i, q, a, b;
     int sum;
     int Person;
    

    
     if (k == len){

           sum = 0;
           for(i=0; i<len; i++){
                    Person= str[i];
                    sum = sum + weakLink[i][Person];
                    }
                    printf("%d\n", sum);
                    if (sum>bestScore){
                       bestScore= sum;
                       }
                     printf("Best : %d\n", bestScore);

               }
          
        
     else {

         for (j=k; j<len; j++) {
        
             Exchange(str, k, j);
            
            RecursivePermute(str, k+1, len, weakLink, bestScore);
            
             Exchange(str, j, k);

         }
     }
}


void Exchange(int *str, int i, int j) {
    
    int temp = str[i];
    str[i] = str[j];
    str[j] = temp;
}

is what i have right now. The RecursivePermute function keeps forgetting what the new bestScore is though, meaning if i initialize it to 0, it will put it back to 0 each time it recurses, which is how I want it to do it at first, but I wanted it to test if the sum was higher, and if it was make it the new best score. Which it does, and prints that out, but the next iteration reduces bestScore back to 0. Can anyone see what im doing wrong?

Ok, I got the bestScore working, got a good chunk of it working, but my inexperience with recursion is interfering again. I don't know how the function realizes its gone through all permutations... so I dont know where to get the final value of bestScore and stuff. Currently i have it printing up bestScore whenever it replaces bestScore.

You should know it's gone through all permutations when it returns to your main(). The score it retains at that point would be the best one.

Ok, got everything working except the names. Im sure there is a way, but I dont know the correct syntax to pass an array of strings into the above functions, and then print out the string at a current spot. Anyone know how to do that? or make a variable size array of strings a global variable? Actually i think I tried doing the second option and it caused a segfault when i called in in the RecursivePermute.

Or the syntax to return just an array would be helpful.

You don't do an array to strings directly. That will cause a segfault. You do an array of char* pointers. Then when you pass the array of pointers to the string, the function accepts it as type char**

Ok, I suppose I dont really know how to do that.

Google is your friend, mate. Plenty of resources on that.

void RecursivePermute(int *str, int k, int len, int **weakLink, char **menNames, char **womenNames);

int main(){
......

char menNames[numCouples][20];
char womenNames[numCouples][20];



RecursivePermute(newArray, 0, numCouples, weakLink, menNames, womenNames);


could you at least tell me why these are imcompatible pointer types? I understand the fact no one wants to do the assignment for me, and that even if they do I wouldnt learn anything. But this was due yesterday and I have to work probably 10 hours today and still study for an exam. I am quite literally running out of time. Ive been at this for like 4 days straight.