安定マッチング問題に対するGale-Shapleyアルゴリズムの実装の例を以下に示す. 入力として,男性の集合,女性の集合,男性の(女性に対する)ランク行列,女性の(男性に対する)ランク行列を受け取り, 女性のパートナーの表を返す関数として定義する.
def gale_shapley(men, women, ranking_matrix_man, ranking_matrix_woman):
'''Gale-Shapleyアルゴリズム(男性からアプローチ)
入力は,男性の集合,女性の集合,男性の(女性に対する)ランク行列,女性の(男性に対する)ランク行列
出力は,女性のパートナー(の集合)
'''
'''
Step 0: 男性とランキングから女性が出力される表woman_of_man_rankingを作る.
'''
woman_of_man_ranking = {}
for m in men:
woman_of_man_ranking[m] = {}
for w in women:
woman_of_man_ranking[m][ranking_matrix_man[m][w]] = w
'''
Step 1: フリーな男性の集合free_menを,男性集合からコピーして作る.
'''
free_men = men[:]
'''
Step 2: 男性が次にアプローチする順位の表next_womanを作り,初期値として0を入れる.
'''
next_woman = {m:0 for m in men}
'''
Step 3: 女性のパートナーの表partnerを作り,初期値として空集合[]を入れる.
'''
partner = {w: [] for w in women}
'''
Step 4: フリーな男性の集合free_manが空でない限り繰り返す.
'''
while len(free_men) > 0:
m = free_men.pop() # フリーな男性の集合から要素を1つ取り出しmとする.
next_woman[m] += 1 # 男性mが次にアプローチするランキングを1増やす.
w = woman_of_man_ranking[m][next_woman[m]] # 男性mが次にアプローチする女性をwとする.
if partner[w] == []: # その女性wのパートナーがいないならば,
partner[w] = m # 男性mを女性wのパートナーとする.
else: # そうではなくて,その女性wにパートナーがすでにいるならば,
if ranking_matrix_woman[w][m] < ranking_matrix_woman[w][partner[w]]: # 今のパートナーよりも良いならば
free_men.append(partner[w]) # 今のパートナーをフリーな男性集合に加え
partner[w] = m # 男性mを新たなパートナーとする.
else: # 今のパートナーの方が良いならば,
free_men.append(m) # アプローチしてきた男性mは再びフリーな男性の集合に戻る.
'''
Step 5: 女性のパートナーの表を返す.
'''
return partner
Gale-Shapleyアルゴリズムを関数として定義したので,次に入力データを定義する. 以下の入力はGaleとShapleyによる原論文のExampleをそのまま持ってきた.
men = ['alpha', 'beta', 'gamma', 'delta']
women = ['A', 'B', 'C', 'D']
ranking_matrix_man = {'alpha': {'A': 1, 'B': 2, 'C': 3, 'D': 4},
'beta': {'A': 1, 'B': 4, 'C': 3, 'D': 2},
'gamma': {'A': 2, 'B': 1, 'C': 3, 'D': 4},
'delta': {'A': 4, 'B': 2, 'C': 3, 'D': 1}}
ranking_matrix_woman = {'A': {'alpha': 3, 'beta': 4, 'gamma': 2, 'delta': 1},
'B': {'alpha': 3, 'beta': 1, 'gamma': 4, 'delta': 2},
'C': {'alpha': 2, 'beta': 3, 'gamma': 4, 'delta': 1},
'D': {'alpha': 3, 'beta': 2, 'gamma': 1, 'delta': 4}}
この入力データを関数に入れると
gale_shapley(men, women, ranking_matrix_man, ranking_matrix_woman)
{'A': 'gamma', 'B': 'delta', 'C': 'alpha', 'D': 'beta'}
確かに安定マッチングが得られる.