Gale Shapley Algorithm

gale-shapley.py

from collections import defaultdict

def stableMatching(n, menPreferences, womenPreferences):
  # Initially, all n men are unmarried
  unmarriedMen = list(range(n))
  # None of the men has a spouse yet, we denote this by the value None
  manSpouse = [None] * n                      
  # None of the women has a spouse yet, we denote this by the value None
  womanSpouse = [None] * n                      
  # Each man made 0 proposals, which means that 
  # his next proposal will be to the woman number 0 in his list
  nextManChoice = [0] * n

  manSpouseMap = defaultdict(lambda: None)
  womanSpouseMap = defaultdict(lambda: None)
  
  while unmarriedMen:
    he = unmarriedMen[0]
    hisPreferences = menPreferences[he]
    she = hisPreferences[nextManChoice[he]]
    herPreferences = womenPreferences[she]
    currentHusband = womanSpouseMap[she]

    nextManChoice[he] = nextManChoice[he] + 1

    if currentHusband == None:
      manSpouseMap[he] = she
      womanSpouseMap[she] = he
      unmarriedMen.remove(he)
    else:
      if herPreferences.index(he) < herPreferences.index(currentHusband):
        worseOffer = herPreferences[herPreferences.index(currentHusband)]
        manSpouseMap[he] = she
        womanSpouseMap[she] = he
        unmarriedMen.remove(he)

        del manSpouseMap[worseOffer]

        unmarriedMen.append(worseOffer)
      # proposed offer is worse
      else:
        if she in womanSpouseMap:
          print("he", he)
        else:
          manSpouseMap[he] = she
          unmarriedMen.remove(he)
  
  for key, val in manSpouseMap.items():
    manSpouse[key] = val

  # print(manSpouse)

  return manSpouse
  
# You might want to test your implementation on the following two tests:
# assert(stableMatching(1, [ [0] ], [ [0] ]) == [0])
# assert(stableMatching(2, [ [0,1], [1,0] ], [ [0,1], [1,0] ]) == [0, 1])
# assert(stableMatching(2, [ [0,1], [1,0] ], [ [1,0], [0,1] ]) == [0, 1])
# stableMatching(3, [ [0,1,2], [1,2,0], [0,2,1] ], [ [1,0,2], [0,1,2], [2,1,0] ])
# assert(stableMatching(3, [ [0,1,2], [1,2,0], [0,2,1] ], [ [1,0,2], [0,1,2], [2,1,0] ]) == [0, 1, 2])
# assert(stableMatching(4, [ [3,1,2,0], [0,3,1,2], [2,3,0,1], [2,0,1,3] ], [ [3,1,0,2], [2,3,1,0], [0,1,3,2], [0,2,1,3] ]) == [1,2,3,0])
# stableMatching(4, [ [3,1,2,0], [0,3,1,2], [2,3,0,1], [2,0,1,3] ], [ [3,1,0,2], [2,3,1,0], [0,1,3,2], [0,2,1,3] ])
# stableMatching(8, [[5, 1, 2, 0, 4, 7, 6, 3], [2, 5, 3, 0, 1, 4, 7, 6], [6, 2, 5, 3, 4, 7, 0, 1], [2, 4, 6, 0, 3, 7, 5, 1], [5, 3, 0, 1, 4, 7, 6, 2], [7, 4, 5, 2, 0, 1, 3, 6], [7, 2, 5, 4, 1, 0, 3, 6], [4, 0, 2, 3, 1, 6, 5, 7]], [[4, 6, 3, 1, 7, 5, 0, 2], [2, 1, 5, 3, 6, 7, 4, 0], [7, 2, 1, 5, 0, 6, 4, 3], [7, 6, 3, 2, 4, 0, 1, 5], [3, 1, 4, 6, 5, 0, 2, 7], [4, 1, 0, 7, 3, 6, 5, 2], [5, 7, 1, 4, 2, 3, 6, 0], [0, 6, 7, 1, 3, 4, 5, 2]])
# assert(stableMatching(4, [[0, 1, 3, 2], [0, 2, 3, 1], [1, 0, 2, 3], [0, 3, 1, 2]], [[3, 1, 2, 0], [3, 1, 0, 2], [0, 3, 1, 2], [1, 0, 3, 2]]) == [1,2,3,0])

# Pseudo code:

# Step 1: While unmarried men, keep proposing the women who do not form a pair
# Step 2: All women who currently do not form a pair, will accept the proposal.
# Step 3: If a proposed woman is given a better offer, the proposed offer is accepted and the pair with current man is broken.
# Step 4: If a proposed woman is given a worse offer, the proposed offer is rejected.
# Step 5: The man moves to propose next woman on list.

Ошибка
RuntimeErrorElement(RuntimeError,Error on line 31:
if herPreferences.index(he) < herPreferences.index(currentHusband):
ValueError: None is not in list
Что делать?

What Python version are you using? I think this code was built to work with Python 3.7