Argthtjtr

I am currently writing a program that demonstrates the Gale-Shapley algorithm.

Description of Gale-Shapley algorithm on wikipedia

I have two lists as input.

preference_boys, which is the boys' preferences on the girls and

preference_girls, which is the girls' preferences on the boys.

In the code, the first ones to choose are the boys and I have successfully managed to pair each boy

with his first choice of the girls.

'''

preference_boys = [[2, 0, 1, 3], [1, 2, 3, 0], [0, 3, 1, 2], [2, 3, 0, 1]]



preference_girls = [[0, 2, 1, 3], [2, 3, 0, 1], [3, 1, 2, 0], [0, 3, 1, 2]]

'''



def couple_maker(preference_boys, preference_girls):

    # stores the couples based on boys first choice of girls

    temporary_couples = 



    single_boys = 



    for boy in range(len(preference_boys)):

        single_boys.append(boy)

    # single_boys = [0, 1, 2, 3]





    while len(single_boys) > 0:

        for single_boy in single_boys:

            for girl in preference_boys[single_boy]:

                temporary_couple = (single_boy, girl)

                single_boys.remove(single_boy)

                temporary_couples.append(temporary_couple)

                break





    return temporary_couples



>>> couple_maker(preference_boys, preference_girls)

[(0, 2), (2, 0), (1, 1), (3, 2)]

Now, I need to make another condition to solve the case when two couples share a single girl.

From my current output of temporary_couples (0, 2) and (3, 2) couples share the same girl.

What methods can I use to compare the preferences of the overlapping girl(the second element

of the tuple in the list) and remove the couple that has the boy with a lower priority to the girl?

One way, would be to group the temporary_couples "by girl" (the 1th index), using something like a defaultdict:

from collections import defaultdict



temp_couples = [(0, 2), (2, 0), (1, 1), (3, 2)]



by_girl = defaultdict(list)



for (b,g) in temp_couples:

    by_girl[g].append((b,g))



for (g,her_temp_couples) in by_girl.items():

    if len(her_temp_couples) > 1:

        print("Girl", g, "has conflicts:", her_temp_couples)

Output:

Girl 2 has conflicts: [(0, 2), (3, 2)]

Then you could go on to resolve the same way the algorithm you cited does.

For clarity, after it's populated in the first loop, by_girl looks like:

{

  0: [(2, 0)], 

  1: [(1, 1)]

  2: [(0, 2), (3, 2)],

  3:                 # Implicitly      

}