图论算法之Gale-Shapley算法

Gale-Shapley算法

近来学习了很有趣的Gale-Shapley算法，又名求婚-拒绝算法。

#!/usr/bin/env python
# _*_ coding:utf-8 _*_
# Some basic testing for your code is provided below. DO NOT modify
# these tests. Your code MUST pass these tests. Note, however, that
# passing these tests does not guarantee that your algorithm is
# correct. You should carry out more testing!def find_stable_matching(MP, WP):""" The input of this function is defined by two lists MP and WPMen and women are numbered 0 through n-1MP[i] encodes the ith man's preferences. It is simply a listcontaining the numbers 0, 1, ... , n-1 in some orderWP[i] encodes the ith woman's preferences. It is simply a listcontaining the numbers 0, 1,... , n-1 in some orderThe output is defined by a list of pairs of the form (i,j)indicating that man i is married to woman jYour output should be the man-optimal stable matching found by theGS-algorithm. """n = len(MP)isManFree = [True] * nisWomanFree = [True] * n# isManProposed=[[False]*n]*nisManProposed = [[False for i in range(n)] for j in range(n)]match = [(-1, -1)] * nwhile (True in isManFree):indexM = isManFree.index(True)if (False in isManProposed[indexM]):indexW = -1for i in range(n):w = MP[indexM][i]if (not isManProposed[indexM][w]):indexW = wbreakisManProposed[indexM][indexW] = Trueif (isWomanFree[indexW]):# isManProposed[indexM][indexW]=TrueisWomanFree[indexW] = FalseisManFree[indexM] = Falsematch[indexM] = (indexM, indexW)else:indexM1 = -1for j in range(n):if (match[j][1] == indexW):indexM1 = jbreakif (WP[indexW].index(indexM) < WP[indexW].index(indexM1)):isManFree[indexM1] = TrueisManFree[indexM] = Falsematch[indexM] = (indexM, indexW)print(match)return matchdef test1():""" basic test for your code """MP = [[0, 1], [1, 0]]WP = [[0, 1], [0, 1]]SM = find_stable_matching(MP, WP)assert ((0, 0) in SM and (1, 1) in SM)def test2():""" basic test for your code """MP = [[0, 1], [0, 1]]WP = [[0, 1], [0, 1]]SM = find_stable_matching(MP, WP)assert ((0, 0) in SM and (1, 1) in SM)def test3():""" basic test for your code """MP = [[0, 1], [0, 1]]WP = [[1, 0], [1, 0]]SM = find_stable_matching(MP, WP)assert ((0, 1) in SM and (1, 0) in SM)if __name__ == "__main__":print("**********test1************")test1()print("**********test2************")test2()print("**********test3************")test3()