Coding Gale Shapely in Python for uneven pairings

Viewed 69

I am wanting to write the Gale-Shapely algorithm in python which can deal with an uneven number of pairings (i.e. more men than woman or more woman than men). The outcome should be the same number of stable matches as the lesser number of men and woman and any left over just do not match. The way in which I have currently implemented it works if number of woman>number of men, but if number of men>number of woman then this produces as infinite loop as the list of 'freeMen' is never empty and the while loop will iterate infinitely. I am struggling to work out how to implement this correctly. Code is below with two lists arguments first comprising a key for each man and values of preferred woman in order and vice versa for the second argument:

def gale_shapely_matching(men_preferences, woman_preferences):
    #create array to store the tempory pairings whilst iterating through matchings
    temporyMatches = []
    #create list of the free men
    freeMen = [user for user in list(men_preferences.keys())]

    #while loop to iterate while the freeMen array is not empty
    while len(freeMen)>0:
        
        for man in freeMen:
            for woman in men_preferences[man]:
                takenMatch = [match for match in temporyMatches if woman in match]

                if takenMatch:
                    current_match = woman_preferences[woman].index(takenMatch[0][0])
                    potential_new_match = woman_preferences[woman].index(man)

                    #check if the the potential new matched man ranks higher in the womans preference (is a lower index). If man is higher preference amend match so as new man replaces previous match
                    if potential_new_match < current_match:
                        
                        freeMen.remove(man)
                        
                        freeMen.append(takenMatch[0][0])
                        takenMatch[0][0] = man
                        break
                    else:
                        pass
                    
                else:   
                    temporyMatches.append([man, woman])
                    freeMen.remove(man)
                    break
    return temporyMatches

Thank you in advance to anyone that can be of help

1 Answers

I think you can change your while len(freeMen)>0: to something like for _ in range(max(len(men_preferences), len(women_preferences))):

Related