stable_marriage_problem.py

def GetMatePrefList(pref_list, person):
    for i in range(len(pref_list)):
        if person == pref_list[i][0]:
            return pref_list[i][1]

def Match(men_pref_list, women_pref_list):
    free_man = []
    free_woman = []
    for man in men_pref_list:
        free_man.append(man[0])
    for woman in women_pref_list:
        free_woman.append(woman[0])

    matched_list = []
    while len(free_man) != 0:
        man = free_man.pop(0)
        print(man, "'s turn")
        mate_list = GetMatePrefList(men_pref_list, man)
        while len(mate_list) != 0:
            woman = mate_list.pop(0)
            print(man, "propose to ", woman)
            if woman in free_woman:
                matched_list.append((man, woman))
                free_woman.remove(woman)
                print(woman, "accept")
                break
            else:
                for i in range(len(matched_list)):
                    if woman == matched_list[i][1]:
                        mate = matched_list[i][0]
                        break
                # check if this man has high rank than woman's mate
                mate_rank = GetMatePrefList(women_pref_list, woman).index(mate)
                man_rank = GetMatePrefList(women_pref_list, woman).index(man)
                # the woman drops old-mate
                if man_rank < mate_rank:
                    print(woman, " replace ", mate, " with ", man)
                    matched_list.remove((mate, woman))
                    matched_list.append((man, woman))
                    free_man.append(mate)
                    break
                else:
                    print(woman, " rejects ", man)

    return matched_list



if __name__ == "__main__":
    men_list = [("Bob", ["Lea", "Ann", "Sue"]), ("Jim", ["Lea", "Sue", "Ann"]), ("Tom", ["Sue", "Lea", "Ann"])]
    women_list = [("Ann", ["Jim", "Tom", "Bob"]), ("Lea", ["Tom", "Bob", "Jim"]), ("Sue", ["Jim", "Tom", "Bob"])]
    matched_list = Match(men_list, women_list)
    print(matched_list)