Gale-Shapley Algorithm Stability Test

Question

I'm a beginner in python coding and am trying to figure out how to test the stability of the Gale-Shapley Algorithm. I understand that for a stable pairing to be made, this means that there's no situation whereby there's 2 people who prefers each other over their assigned partner.

The data of participants' preferences is as follows:

preference = [["boy1",1,3,2,4], ["boy2",1,2,4,3],["boy3",1,2,3,4],["boy4",2,3,1,4],["girl1",2,1,3,4],["girl2",4,3,2,1],["girl3",1,2,3,4],["girl4",3,4,2,1]]

For example, for preference[0], boy1's ranking for girl1 is 1, girl2 is 3, girl3 is 2, girl 4 is 4. This means that the list goes: ["boy1", (ranking of girl1), (ranking of girl2), (ranking of girl3), (ranking of girl 4)].

An example of a solution of pairings is as follows:

solution1 = [["boy1","girl1"],["boy2","girl3"],["boy3","girl2"],["boy4","girl4"]

I'm trying to come up with a function that produces true if solution is stable and false if the solution isn't stable, given the preference, solution and number of couples.

I've tried using pandas and numpy but I keep getting stuck with many for loops and if and problems with indexing as I'm not very familiar with any of these python libraries. I'm now trying to go back to basic and see if it's possible to do it. However, as I'm doing it, I realize that I kept using for loops and it won't be as efficient. Below is my incomplete code, please do advise on what I should do to improve the efficiency of this incomplete code - and if it's possible to execute my current incomplete code once it's complete. Please do suggest any python libraries that I can use too, any suggestions are greatly appreciated!

def teststability(n, preference, solution):
  for i in solution[i]:
    fpo = solution[i][1][1]
    for j in preference[j]:
      if solution[i][0] == preference[j][0]:
        rank = preference[j][fpo]
        if rank == 1:
          continue
        else:
          for k in pref[j][k]:
            if pref[j][k] < rank:
              lst.append("girl"+str(k))
            else:
              continue

Answer 1

You don't Pandas or Numpy for this, as it's a classic algorithmic SAT problem, and not one of data. (If you need to apply a given solution algorithm to a large array of pairs, then Pandas might be useful.)

The algorithm is implemented in the QuantEcon/MatchingMarkets package.

Lastly, I'd note that it's a little confusing that you're using lists made of strings and integers. I'd suggest dict of male-to-female and female-to-male preferences, eg:

female_prefs = {1: [2, 1, 3, 4], 2: [4, 3, 2, 1], 3: [1, 2, 3, 4], 4: [3, 4, 2, 1]}