Title: Make stable appointments in C#

This example assumes you have people who must sign up for a limited number of appointments. Each person is allowed to select first, second, and third choices. The program assigns people to appointments in a "stable" way where "stable" means no two people would be willing to trade appointments.

The Person class represents a person and his or her preferences.

The following code makes the assignments.

// Make assignments private void btnGo_Click(object sender, EventArgs e) { // Get the Persons' preferences. string txt = txtPreferences.Text; while (txt.EndsWith("\r\n")) { txt = txt.Substring(0, txt.Length - "\r\n".Length); } txt=txt.Replace("\r\n", "\n"); string[] lines = txt.Split('\n'); int num_people = lines.Length; Person[] people = new Person[num_people]; for (int i = 0; i < num_people; i++) people[i] = new Person(lines[i]); // Clear assignments. Person[] assigned_to = new Person[Person.NUM_CHOICES]; for (int i = 0; i < Person.NUM_CHOICES; i++) { assigned_to[i] = null; } // Make initial choice assignments. for (int pref = 0; pref < Person.NUM_PREFERENCES; pref++) { // Try to assign this choice for Persons. foreach (Person per in people) { // See if this Person has an assignment yet. if (per.Assignment < 0) { // This Person is unassigned. // See if this choice is available. int desired_choice = per.Preferences[pref]; if (assigned_to[desired_choice] == null) { // Assign this Person. assigned_to[desired_choice] = per; per.Assignment = desired_choice; } } } } // Assign anyone without an assignment. foreach (Person per in people) { // See if this Person has an assignment yet. if (per.Assignment < 0) { // This Person is unassigned. // Find an available choice. for (int i = 0; i < Person.NUM_CHOICES; i++) { if (assigned_to[i] == null) { // Assign this Person. assigned_to[i] = per; per.Assignment = i; break; } } } } // Try to improve the assignments. bool had_improvement; do { had_improvement = false; // Look for profitable swaps. foreach (Person per in people) { foreach (Person per2 in people) { int per2_assignment = per2.Assignment; int per_assignment = per.Assignment; // See if per and per2 should swap. int old_cost = per.Value + per2.Value; int new_cost = per.ValueOf(per2_assignment) + per2.ValueOf(per_assignment); if (new_cost < old_cost) { // Make the swap. per.Assignment = per2_assignment; per2.Assignment = per_assignment; assigned_to[per_assignment] = per2; assigned_to[per2_assignment] = per; had_improvement = true; } } } } while (had_improvement); // Display the results. txtAssignments.Text = AssignmentSummary(assigned_to, people); }

The code reads preference information from a text box and uses it to build the Person objects.

Next the code makes initial assignments. For each preference level (in this example, people rank three appointments 0, 1, or 2), the code examines the Person objects. If a Person is not yet assigned and that Person object's preference for this level has not been assigned, the program makes that assignment.

For example, suppose the program is looking at preference 1 (the second choice). Sally has not been assigned an appointment yet and her choice number 1 is appointment slot 6. If that slot is not already taken by another Person, then the program assigns it to Sally.

After it has made these preferential assignments, the program assigns any unassigned Person to any available appointment.

Next the program enters a loop looking for improvements. For each pair of Person objects, the program determines whether those persons should trade appointments. For example, suppose Bill was assigned his first choice appointment number 3 and Cindy was assigned appointment number 7, which she did not list as one of her choices. Suppose Bill listed appointment 7 as his third choice and Cindy listed appointment 3 as her second choice. In this case, the program swaps Bill's and Cindy's appointments. It prefers the third/second choices over the first/none choices.

Note that this example does not guarantee any sort of optimality. There may be more complicated trades involving more than two people that lead to a better final solution. I may work on another program to look at this more closely.

Note also that in real life you cannot compare the values of peoples' choices directly. For example, suppose you are available for any of the appointments but I have work during all but one. Then in some sense my first choice is more important than all of your choices. If I don't get my first choice, I need to take extra measures such as getting time off of work.

Download the example to experiment with it and to see additional details.