SMP Example

smp.py

# Stable Matching Problem, demonstrating the Gale-Shapley Algorithm
# for creating a stable matching between two sets of equal size

'''
Array representing the n Residents and n Hospitals
- in this case, n = 4
'''
ResidentAndHospital = [[3, 5, 4, 6],
               [4, 3, 6, 5],
               [4, 5, 3, 6],
               [6, 3, 4, 5],
               [1, 0, 2, 3],
               [0, 2, 3, 1],
               [2, 3, 0, 1],
               [3, 0, 1, 2]]

'''
Initialize dictionary to hold the pairs of matchings
'''
matching = {}

''' 
Initialize proposed Hospital array
- no Hospitals are proposed to at start
'''
proposedTo = [None] * 4

''' 
Initialize free Residents
- all Residents are free at start of execution
'''
freeResident = [0, 1, 2, 3]

while len(freeResident) != 0:
    r = freeResident.pop(len(freeResident) - 1)
    rList = ResidentAndHospital[r]
    for h in rList:
        if proposedTo.__contains__(h):
            if ResidentAndHospital[h].index(matching[h]) < ResidentAndHospital[h].index(r):
                continue
            else:
                oldResident = matching[h]
                matching[h] = r
                freeResident.append(oldResident)
                break
        else:
            proposedTo.append(h)
            matching[h] = r
            break

# Show the results
for hospital in matching:
    print("Hospital {0} employs Resident {1}".format(hospital, matching[hospital]))