最近这几周在复习微机原理，不可避免地重燃了对硬件的兴趣，一度想要拿下一张树莓派玩玩，好在这东西不便宜，思来想去还是决定暂时放放。
一直有在考虑自己未来的发展方向，自动驾驶还是交通运输，这对我来说是一个很难决定的事情。回过头来想，其实现在确实想不出一个答案，一是积累不够，二是眼界尚浅。于是决定静下心来去学习和沉淀，看着书架上好久没翻开的《算法设计》，就决定从这里开始了！
希望我能把这个系列做下去，能把这本书啃完。
因为是学习记录，内容上更多是代码展示和思考过程，不会对原文内容进行太监传话，如果有想一起学的可以考虑书（封面上的这本）和博客一起食用，也欢迎关注我的公众号：补考日记。
稳定匹配
稳定匹配描述了这样一个问题：现有n位男性和n位女性，每位男性对n位女性都有一个好感度排名，当然每位女性对n位男性也有一个好感度排名。我们的目标是求解这样一个匹配集合，它满足一夫一妻制（完美匹配），且不存在这样两个元素（m1,w1）（m2,w2）其中m1更喜欢w2，w2也更喜欢m1（稳定匹配）。
算法
代码
<1>定义人物类与相关函数
人物类包含属性有名字，是否未进入订婚状态，好感度列表，已匹配过列表，伴侣；函数有检验好感度排名，更改人物状态。
# ------------------------class and function------------------------
class Person:
def __init__(self, name, free, prefer_list, matched_list, mate):
self.name = name
self.free = free
self.prefer_list = prefer_list
self.matched_list = matched_list
self.mate = None
def check_prefer(w, m1, m2):
prefer_m1 = w.prefer_list.index(m1)
prefer_m2 = w.prefer_list.index(m2)
if prefer_m1 < prefer_m2:
return 1
else:
return 0
def change_state(i, j):
i.free = 0
j.free = 0
i.mate = j
j.mate = i
i.matched_list.append(j)
# ------------------------class and function------------------------<2>初始化人物对象
我的面向对象学的很一般，在设计人物类的时候碰到了问题。person.mate这一属性的type是Person类，这使得我在初始化类对象的时候卡壳了，于是只能用下面的呆瓜方法初始化。（写了个生成字符串的脚本，还挺快？）做了张表方便大家看好感度排名。
| w1 | w2 | w3 | w4 | |||||
| m1 | 3 | 3 | 1 | 1 | 2 | 4 | 4 | 2 |
| m2 | 1 | 1 | 3 | 3 | 4 | 2 | 2 | 4 |
| m3 | 4 | 2 | 2 | 2 | 3 | 3 | 1 | 1 |
| m4 | 2 | 4 | 4 | 4 | 1 | 1 | 3 | 3 |
# ------------------------initialize person------------------------
w1 = Person('w1', 1, [], [], None)
w1.mate = w1
w2 = Person('w2', 1, [], [], None)
w2.mate = w2
w3 = Person('w3', 1, [], [], None)
w1.mate = w3
w4 = Person('w4', 1, [], [], None)
w1.mate = w4
m1 = Person('m1', 1, [], [], None)
m1.mate = m1
m2 = Person('m2', 1, [], [], None)
m2.mate = m2
m3 = Person('m3', 1, [], [], None)
m3.mate = m3
m4 = Person('m4', 1, [], [], None)
m4.mate = m4
w1.prefer_list = [m2, m3, m1, m4]
w2.prefer_list = [m1, m4, m2, m3]
w3.prefer_list = [m4, m2, m3, m1]
w4.prefer_list = [m3, m1, m4, m2]
m1.prefer_list = [w2, w3, w1, w4]
m2.prefer_list = [w1, w4, w2, w3]
m3.prefer_list = [w4, w2, w3, w1]
m4.prefer_list = [w3, w1, w4, w2]
# ------------------------initialize person------------------------<3>匹配
这一部分才是这篇推送的重点，实际上就是对上面图里算法的实现。实现过程中遇到的问题：1.算法结束标志，一开始我是构建了匹配结果列表，后来嫌麻烦，换成了下面的count，个人觉得挺好；2.break，刚写完的时候没写这俩break，导致算法一直结束不了，后来加了两条print用来debug才找到这个问题（真的很喜欢用print来调试，想要什么输出什么，软件自带的信息量太多了）；3.循环列表，我用了4*[m1, m2, m3, m4]，这是因为G-S算法的时间复杂度最大为O(n^2)，但我这样写是会导致算法运行时间变长的。
# -----------------------------------begin match-----------------------------------
def match():
count = 1
while count != 0:
for i in [m1, m2, m3, m4, m1, m2, m3, m4, m1, m2, m3, m4, m1, m2, m3, m4]:
if i.free:
for j in i.prefer_list:
if j in i.matched_list:
continue
else:
if j.free or j.mate is j:
change_state(i, j)
# print('match:{},{}'.format(i.name, j.name))
break
else:
if check_prefer(j, i, j.mate):
j.mate.free = 1
change_state(i, j)
# print('match:{},{}'.format(i.name, j.name))
break
else:
i.matched_list.append(j)
count = m1.free + m2.free + m3.free + m4.free
# print(count)
# -----------------------------------begin match-----------------------------------<4>检验
# ---------------------main---------------------
match()
for i in [m1, m2, m3, m4]:
print('[{},{}]'.format(i.name, i.mate.name))
# ---------------------main---------------------<5>最终结果
[m1,w2]，[m2,w1]，[m3,w4]，[m4,w3]