Gale-Shapley

GS算法全称Gale-Shapley算法，用于解决Stable matching问题，Gale-Shapley算法效率要高于Brute Force算法 Brute Force 算法interation的次数是N! 而gs算法interation 次数是N^2.

Brute Force 算法 interation的次数是N!
gs算法 interation 次数是N^2

---

基本思想

GS算法 aka. Get-rid-of-single算法 手动狗头

基本思想

---

while ((some man is free and has not proposed to every woman) and (do choose such a man)):
# w is 1st woman on m's list to whom m has not yet proposed
if (w is free):
assign m to w
esle if (w prefers m to her fiance' m1):
assign m to w and m1 is free
else:
w reject m

---

For Example

4 men(W-Z)with preference list (left)
4women(A-D)with preference list(right)

Implication

gs算法.jpg

Implication by Python

'

!/user/bin/env python

-- coding:utf-8 --

Author : Zhuangzhi Gao

Date :2021.10.18

from collections import deque

初始化

Man = ["W","X","Y","Z"]
Woman = ["A","B","C","D"]

偏爱列表

pre_boy_to_girl = [[2,1,3,4],[3,2,1,4],[2,3,1,4],[2,1,4,3]]
pre_girl_to_boy = [[2,1,3,4],[1,3,2,4],[4,3,1,2],[2,1,3,4]]

def find_partner(Man,Woman,pre_boy_to_girl,pre_girl_to_boy):
#写一个字典
corrent_Man = {Man[0]:None,Man[1]:None,Man[2]:None,Man[3]:None}
corrent_Woman = {Woman[0]:None,Woman[0]:None,Woman[0]:None,Woman[0]:None}
index = len(Man)

#建立队列选择女孩
new_match = {}
for i in range(index):
    new_match[Man[i]] = deque();
    argsort_p = sorted(range(index), key = lambda k:pre_boy_to_girl[i][k])
    for j in range(index):
        new_match[Man[i]].append(Woman[argsort_p[j]])

#女孩选择男孩字典
sort_girl = {}
for i in range(index):
    sort_girl[Woman[i]] = {}
    for j in range(index):
        sort_girl[Woman[i]][Man[j]] = pre_girl_to_boy[i][j]

while None in new_match.values():
    for i in range(index):
        bid = Man[i]
        if new_match[bid]:
            continue
        else:
            select = new_match[bid][0]
            if corrent_Woman[select] == None:
                #女孩没对象两者结合
                corrent_Man[bid] = select
                corrent_Woman [select] = bid
                new_match[bid].popleft()
            else:
                if sort_girl[select][corrent_Woman[select]]<sort_girl[select][bid]:
                    new_match[bid].popleft()
                else:
                    corrent_Man[corrent_Woman[select]]= None
                    corrent_Man[bid] = select
                    corrent_Woman[select] = bid
                    new_match[bid].popleft()
return corrent_Man

print (find_partner(Man,Woman,pre_boy_to_girl,pre_girl_to_boy))

'