Title: Make stable appointments in Python

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 example mostly consists of two pieces: a Person class that represents people and their preferences, and the main assignment algorithm.

Person Class

class Person: def __init__(self, index, preferences): names = [ 'Amy', 'Ben', 'Cam', 'Dan', 'Eve', 'Fae', 'Gar', 'Han', 'Ivy', 'Jan', 'Kat', 'Lea', 'Mac', 'Nia', 'Oly', 'Pam', 'Qar', 'Rod', 'Sid', 'Taj', 'Uli', 'Van', 'Win', 'Xia', 'Yaz', 'Zeb' ] self.name = names[index] self.preferences = preferences self.assignment = None def __str__(self): return f'{self.name}: {self.preferences}' def value(self): '''Return this person's value for their current assignment.''' return self.value_of(self.assignment) def value_of(self, assignment): '''Return the person's value for this assignment.''' # Return DONT_WANT if the person did not list this choice. DONT_WANT = 1000 # DONT_WANT is slightly better than NO_ASSIGNMENT NO_ASSIGNMENT = 1001 if assignment is None: return NO_ASSIGNMENT if assignment not in self.preferences: return DONT_WANT return self.preferences.index(assignment)

The preferences list gives the appointment numbers preferred by this person in order. For example, if the person's first choice is appointment 3, second choice is appointment 1, and third choice is appointment 0, the preferences list will be [3, 1, 0].

The __str__ dunder method simply returns the person's name and preferences.

The value method returns the value of this person's current assignment by calling the value_of method.

The value_of method returns the index of an assignment in this person's preferences list. For example, if the assignment is appointment 3 and this person has appointment 3 as their first preference, then the method returns 0 (the index of that preference).

If there is no assignment, the method returns 1001 to represent a really bad assignment. If the assignment is not in the person's preferences list, the method returns 1000. That's still a bad assignment but it's better than no assignment.

Assignment Algorithm

def assign(self): '''Make assignments.''' num_assignments = int(self.num_appointments_entry.get()) # Clear assignments. self.assigned_to = [None for i in range(num_assignments)] # Make initial assignments. for pref in range(self.num_preferences): # Try to assign this choice for the people. for person in self.people: # See if this Person has an assignment yet. if person.assignment is None: # This Person is unassigned. # See if this choice is available. desired_choice = person.preferences[pref] if self.assigned_to[desired_choice] is None: # Assign this person to this choice. self.assigned_to[desired_choice] = person person.assignment = desired_choice # Assign anyone who doesn't have an assignment. for person in self.people: # See if this Person has an assignment. if person.assignment is None: # This Person is unassigned. Find an available choice. for i in range(len(self.assigned_to)): if self.assigned_to[i] is None: # Assign this Person. self.assigned_to[i] = person person.assignment = i break # Try to improve the assignments. had_improvement = True while had_improvement: had_improvement = False # Look for profitable swaps. for person1 in self.people: for person2 in self.people: assignment1 = person1.assignment assignment2 = person2.assignment # See if person1 and person2 should swap. old_cost = person1.value() + person2.value() new_cost = \ person1.value_of(assignment2) + \ person2.value_of(assignment1) if new_cost < old_cost: # Make the swap. person1.assignment = assignment2 person2.assignment = assignment1 self.assigned_to[assignment1] = person2 self.assigned_to[assignment2] = person1 had_improvement = True # Display the assignments. self.show_assignments()

Next, it loops through the preference numbers: first choice, second choice, etc. For each preference number, the code loops through the people. If a person is not yet assigned and their choice for this preference number is not yet assigned to someone else, the code assigns it.

For example, suppose we're looking at preference number 2, which is the third choice (because indexes begin with 0). Now suppose Bob does not yet have an assignment because his first and second choices were assigned to someone else. Now if Bob's third choice has not been given to someone else, the program assigns it to Bob.

After it makes the initial assignments, the code loops through the people and tries to give anyone left over an assignment. For example, suppose all of Fae's preferences were assigned to other people. The code assigns Fae to the next available appointment if there is one.

(Note that, if there are more people than appointments, some people won't get any appointment. The way the code is written, people who come later in the list will be the ones who won't be assigned. If you don't want to punish people for having the last name Zimmerman or Zeigler, don't arrange the list alphabetically. You could arrange it randomly or put people in the list in the order in which they turned in their preferences.)

After it has made the initial assignments and tried to give everyone at least some assignment, the code enters a while loop where it tries to make improvements. Inside the loop, it compares each person to every other person. If swapping their appointments would give a better result, the program swaps them and the while loop continues. The loop runs until it cannot find any more swaps.

Conclusion

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.