Gale-Shapley algorithm not functioning properly

Question

So I'm trying to code up the Gale-Shapley algorithm in Python, where men propose to women (ideally, the sexes can be reversed). I organized all men, women, and rankings in one dictionary, where the men/women are the keys, and their rankings are the values (as a list). Thus I have a test dictionary that looks like this:

import pandas as pd
import numpy as np
import math

dic = {'m1': ['w1', 'w2', 'w3', 'w4', math.nan],
 'm2': ['w4', 'w3', 'w2', 'w1', math.nan],
 'm3': ['w4', 'w3', 'w1', 'w2', math.nan],
 'm4': ['w1', 'w4', 'w3', 'w2', math.nan],
 'm5': ['w1', 'w2', 'w4', math.nan, math.nan],
 'w1': ['m2', 'm3', 'm1', 'm4', 'm5'],
 'w2': ['m3', 'm1', 'm2', 'm4', 'm5'],
 'w3': ['m5', 'm4', 'm1', 'm2', 'm3'],
 'w4': ['m1', 'm4', 'm5', 'm2', 'm3']}

So printing the dictionary gives

{'m1': ['w1', 'w2', 'w3', 'w4', nan],
 'm2': ['w4', 'w3', 'w2', 'w1', nan],
 'm3': ['w4', 'w3', 'w1', 'w2', nan],
 'm4': ['w1', 'w4', 'w3', 'w2', nan],
 'm5': ['w1', 'w2', 'w4', nan, nan],
 'w1': ['m2', 'm3', 'm1', 'm4', 'm5'],
 'w2': ['m3', 'm1', 'm2', 'm4', 'm5'],
 'w3': ['m5', 'm4', 'm1', 'm2', 'm3'],
 'w4': ['m1', 'm4', 'm5', 'm2', 'm3']}

Then my algorithm looks like this:

couples = [] #initialize list of marriages

#men-proposing algorithm
#for women-proposing, switch the ""'m' in man" to "'w' in man"

#this for loop does one round of proposals/rejections, until men's rankings are exhausted
for man, ranks in dic.items():
    if man in [tup[0] for tup in couples]: #check man isn't already engaged
        continue #go to next man if engaged
    else:
        if 'm' in man: #ensure it's a man
            if not pd.isna(ranks[0]): #check man hasn't already proposed to everyone on his list
                w = ranks[0]
                ranks.pop(0)
                engage = (man,w)
                sub_cup = [tup for tup in couples if tup[1] == w]
                if sub_cup: #check if woman is already engaged
                    other_man = sub_cup[0][0]
                    if dic[w].index(other_man) > dic[w].index(man): #if man is preferred to other man
                        couples.remove(sub_cup[0])
                        couples.append(engage)
                else: #unconditionally add couple if woman isn't engaged
                    couples.append(engage)

The problem, however, is that already-engaged men are proposing to women. In the algorithm, if a man is engaged, he's supposed to not make a proposal. So Round 1 works perfectly, and we have, as the couples:

[('m1', 'w1'), ('m2', 'w4')]

and the new dictionary is:

{'m1': ['w2', 'w3', 'w4', nan],
 'm2': ['w3', 'w2', 'w1', nan],
 'm3': ['w3', 'w1', 'w2', nan],
 'm4': ['w4', 'w3', 'w2', nan],
 'm5': ['w2', 'w4', nan, nan],
 'w1': ['m2', 'm3', 'm1', 'm4', 'm5'],
 'w2': ['m3', 'm1', 'm2', 'm4', 'm5'],
 'w3': ['m5', 'm4', 'm1', 'm2', 'm3'],
 'w4': ['m1', 'm4', 'm5', 'm2', 'm3']}

So in Round 2, only men 3, 4, and 5 are supposed to make proposals. But when I run the for loop again, everyone makes a proposal, as evidenced by how the dictionary is altered:

{'m1': ['w3', 'w4', nan],
 'm2': ['w2', 'w1', nan],
 'm3': ['w1', 'w2', nan],
 'm4': ['w3', 'w2', nan],
 'm5': ['w4', nan, nan],
 'w1': ['m2', 'm3', 'm1', 'm4', 'm5'],
 'w2': ['m3', 'm1', 'm2', 'm4', 'm5'],
 'w3': ['m5', 'm4', 'm1', 'm2', 'm3'],
 'w4': ['m1', 'm4', 'm5', 'm2', 'm3']}

And the new list of couples is

[('m1', 'w2'), ('m2', 'w3'), ('m4', 'w4')]

which shouldn't happen; m1 shouldn't propose to w2 since he's engaged to w1, and similarly, m2 shouldn't propose to w3.

I thought my initial if-else statement in the for loop ensures only unengaged men make proposals, but it seems that's not the case. Or perhaps something else is wrong?

Thank you!

Answer 1

Sorry, it's fixed now (and I cleaned the code so the original error should be reproducible)! I realized that every time I ran the loop, I re-initialized the list of couples, so whenever the code checked if a man was in the list of couples, the man would never be in it.