Hospital-Student Matching using Gale-Shipley Algorithm

match.py

students = ['A', 'B', 'C']
hospitals = ['X', 'Y', 'Z']

prefs = {
    'X': ['B', 'A', 'C'],
    'Y': ['A', 'B', 'C'],
    'Z': ['A', 'B', 'C'],
    'A': ['X', 'Y', 'Z'],
    'B': ['Y', 'X', 'Z'],
    'C': ['X', 'Y', 'Z']
}

# a useful transformation of the preferences
rank = {
    'X': {'A':2, 'B':1, 'C':3},
    'Y': {'A':1, 'B':2, 'C':3},
    'Z': {'A':1, 'B':2, 'C':3}
}

# reverse prefs for convenience in implementation
for x in prefs:
    prefs[x].reverse()

free_students = list(students)  # initialize list of free students
M = {}                          # initialize matching dictionary

while len(free_students) > 0:
    s = free_students.pop()
    # if s has not proposed to everyone
    if len(prefs[s]) > 0:
        # get the top remaining preference
        h = prefs[s].pop()
        if h not in M:
            M[h] = s
        else:
            s2 = M[h]
            if rank[h][s] < rank[h][s2]:
                M[h] = s
                free_students.append(s2)
            else:
                # s is still free
                free_students.append(s)

print(M)