Моя Python реализация алгоритма Гейла-Шейпли дает неверные результаты

Question

Добрый день! Я пытаюсь реализовать алгоритм Гейла-Шепли в python. Цель алгоритма - составить список мужчин и женщин (оба списка имеют одинаковую длину), а также список предпочтений для каждого мужчины и женщины. Он также известен как алгоритм стабильного брака. Псевдокод выглядит следующим образом.

Пока существует неженатый мужчина:

1. Выберите произвольного не состоящего в браке мужчину M

2. Выберите лучшую женщину W из его список, кому он еще не предложил

3. Если W свободна или предпочитает M своему нынешнему мужу, тогда женись на M и W

Моя Python реализация алгоритма Гейла-Шепли дает результат [1, 2, нет, 0], когда:

n = 4,
menPreferences = [[0, 1, 3, 2 ], [0, 2, 3, 1], [1, 0, 2, 3], [0, 3, 1, 2]]

womenPreferences = [[3, 1, 2, 0] , [3, 1, 0, 2], [0, 3, 1, 2], [1, 0, 3, 2]])

Вот мой код:

def stableMatching(n, menPreferences, womenPreferences):

# Do not change the function definition line.



  # 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

# While there exists at least one unmarried man:

  while unmarriedMen:

    # Pick an arbitrary unmarried man

    he = unmarriedMen[0]

    # Store his ranking in this variable for convenience

    hisPreferences = menPreferences[he]

    # Find a woman to propose to

    she = hisPreferences[nextManChoice[he]]

    # Store her ranking in this variable for convenience

    herPreferences = womenPreferences[she]

    # Find the present husband of the selected woman (it might be None)

    currentHusband = womanSpouse[she]


    #Variable that helps us to keep track of when a man is made single

    divorcedMan = None

    #The man currently making the proposal (Incrementing Variable)

    manProposing = 0



    #For the current list of married men:

    while manProposing < len(unmarriedMen):

      #Chooses the next man to make a proposal

      he = unmarriedMen[manProposing]

      #Establishing the parameters aka the preferences for the man

      #currently making the proposal

      # Store his ranking in this variable for convenience

      hisPreferences = menPreferences[he]

      # Find a woman to propose to

      she = hisPreferences[nextManChoice[he]]

      # Store her ranking in this variable for convenience

      herPreferences = womenPreferences[she]

      # Find the present husband of the selected woman (it might be None)

      currentHusband = womanSpouse[she]


      #If the next preference for this man is not married

      if currentHusband == None:
        #The woman becomes married to this man

        womanSpouse[she] = he

        #The man becomes married to this woman

        manSpouse[he] = she

        #The index of the currently matched man is incremented

          if (len(unmarriedMen) - nextManChoice[he]) >= 2:

            nextManChoice[he] += 1

            #This indicates that the man is no longer single

            unmarriedMen[he] = -1

            #The next man is moved on to

            manProposing += 1



        else:

        #If the man proposing making a proposal is more preferred by her

          if herPreferences.index(he) < herPreferences.index(currentHusband):

              #She leaves her current husband

            divorcedMan = currentHusband

            manSpouse[divorcedMan] = None

            #The proposing becomes her husband

            womanSpouse[she] = he

            #currentHusband = he

            #She becomes his wife

            manSpouse[he] = she

            #The index of the currently matched man is incremented

            if (len(unmarriedMen) - nextManChoice[he]) >= 2:

              nextManChoice[he] += 1

            #This indicates that the man is no longer single

            unmarriedMen[he] = -1

            #This will look at the next man that is to do the next proposal

            manProposing += 1

            #The new divorcee man is placed back in the list

            for man in unmarriedMen:

            if (unmarriedMen.index(man) == divorcedMan) and (man == -1):

              unmarriedMen[unmarriedMen.index(man)] = divorcedMan

              break

            else:
                 if (divorcedMan < man):

              unmarriedMen.insert(unmarriedMen.index(man), divorcedMan)

              break


            #Resetting the variable divorcedMan

            divorcedMan = None

    #Variable for temporarily holding newly formed list of married men

    temp = []

    #Forms new list of married men

    for bachelor in unmarriedMen:

      if bachelor != -1:

          temp.append(bachelor)

    unmarriedMen = temp

 return manSpouse

Я изо всех сил пытаюсь найти логические ошибки в моем коде. Может ли кто-нибудь помочь мне определить их? Любая помощь будет очень признательна.