Python script for allocating elective subjects based on "College Admissions and the Stability of Marriage, by D. Gale and L. S. Shapley"

stable_elective.py

import pandas as pd
import sys

if __name__ == "__main__":

    if len(sys.argv) != 3:
        print("usage: python3 stable_elective.py <electivelist> <sheetname>", file = sys.stderr)
        sys.exit(1)

    # Note: Assuming Excel file with columns having following names:
    # MIS Name GPA 1 2 3 4 5 6
    # 1, 2, 3, 4, 5, 6 can take values from following list:

    list_of_electives = ["AMPT", "WST", "GML", "FOF", "DSP", "ADS"]
    no_of_electives = len(list_of_electives)
        
    electivelist = sys.argv[1]
    sheetname = sys.argv[2]

    # clean up the data that has been foolishly filled
    ef = pd.read_excel(electivelist, sheetname)
    ef.replace('\n', '', regex = True, inplace = True)
    ef.replace(u'\xa0', '', regex = True, inplace = True)


    # if capacity were 40, then everyone will get a course- no fun
    CAPACITY = 20

    # ugly hack here, but works
    allocations = {}
    for elective in list_of_electives:
        allocations[elective] = []

    # all candidates will apply in first round
    rejected = set(ef.MIS)

    n = len(ef)

    for i in range(no_of_electives):
        pref = 1 + i
        for j in range(n):
            # only candidates rejected in previous round will apply in the next round
            if ef.iloc[j]['MIS'] in rejected:
                # add candidate to tentative list
                preference = ef.iloc[j][pref]
                crit = (ef.iloc[j]["MIS"], ef.iloc[j]["GPA"])
                allocations[preference].append(crit)


        selected_this_round = set()
        for course in allocations.keys():
            # remove all candidates exceeding capacity from list
            allocations[course].sort(key = lambda x: x[1], reverse = True)
            allocations[course] = allocations[course][:CAPACITY]
            selected_this_round.update([x[0] for x in allocations[course]])
        
        # calculate remaining candidates
        rejected = set.difference(rejected, selected_this_round)

        # humiliate them
        print(rejected, file = sys.stderr)

        # if everyone has got a course, exit!
        if len(rejected) == 0:
            break

    
    for course in allocations.keys():
        for alloc in allocations[course]:
            print(alloc[0], alloc[1], ef.loc[ef["MIS"] == alloc[0]].Name.item(), course, sep = '\t')


# Reference: "College Admissions and the Stability of Marriage, D. Gale and L. S. Shapley, The American Mathematical Monthly, Vol. 69, No. 1 (Jan., 1962), pp. 9-15"