PROGRAMMING ASSIGNMENT 9

Stable matching

Write a program to produce a stable matching of students to eating clubs, using the stable marriage algorithm. The clubs provide lists of students, in order of preference; and the students provide lists of clubs, in order of preference. Your program is to produce an assignment of students to clubs with the property that all clubs that any student X would prefer over the one assigned are filled with students that they prefer to X. This is equivalent to the condition that all students that any club C would prefer over the ones assigned have been assigned to clubs that they prefer to C.

The algorithm for this problem is described on pages 499-504 in the text. This description relates to a simpler situation that is equivalent to clubs' having only one member. Not all the code is given for this method, but the method is fully described. Your task for this program is to fill in the missing code, then to figure out how to use it to solve the more general problem described above.

First, complete the program described in the text and get it to run on the example given in the text, using a simple input format, like the example in the online version of this document, where you read the preference matrices directly and use them to initialize the various data structures described in the text. You do not need to submit this version of your program.

To solve the problem of matching students to clubs, assume that there are less than 25 clubs and less than 1000 students, and use the input format shown in the following example: 

         3 7 
         2 1 2 
         a 1 3 7 2 4 6 5 
         b 2 3 1 4 6 5 7 
         c 1 6 4 5 2 7 3 
         1 a b c 
         2 b c a 
         3 a c b 
         4 a b c 
         5 a b c 
         6 c a b 
         7 b a c
The first line says that there are three clubs and seven students. The clubs are named with lower case letters starting at a, and the students are named with integers starting at 1. The second line says that the three clubs have space for 2, 1, and 2 students, respectively. The next three lines give the preference lists for the clubs; then the next seven lines give the preference lists for the students. Your output should be a stable assignment, such as 1a 2b 3a 4c 6c . In this case, with more students than slots available, two students are not assigned to any club. This is still stable, as all clubs are filled with students than rank higher on their lists than the unassigned students.

You can use your basic stable marriage implementation to solve this problem, but you will need to understand what the algorithm does in order to figure out how to convert the given input into the square matrices that the program uses. Be sure to think about how you are going to do this before sitting down to code it. Once you have developed the basic idea, the coding is straightforward.

Extra Credit. If the preference lists are incomplete, a stable configuration may not be possible. Modify your program to deal with incomplete lists, produce a stable configuration if one exists, and report that none exists if that is the case.

Due: 11:59PM Thursday, April 25.