时间：20210928
背景：有个相亲活动，需要暗地里给男女进行匹配，毕竟明面上直接说不喜欢哪个异性总是尴尬的。匹配的话，方法众多，并不能让每个人都满意，根据各自的意向，总能计算整体意向都不错的。
太长了不看，直接操作：
线下让N对男女：
- 写个小纸条，各自给N个异性排序，更喜欢的排在前面
- 得到：
- 女生的选择：womanChoices
- 女1：男2，男5，男1，....
- 女2：...
- ...
- 女N：...
- 男生的选择：manChoices
- 同理
- 女生的选择：womanChoices
操作：
- 进入网站：代码在线运行 - 在线工具
- 选择python
- 不要用python3
- 代码复制进去
- 修改代码里的两个变量：womanChoices、manChoices
- 将之前线下统计得到的，放在对应位置
- 点击“执行Run”
- 右侧出结果即可
算法：GS算法（盖尔-沙普利算法（Gale-Shapley algorithm））
算法思想：略
算法伪代码：
样例解释：
1、1对男女，不考虑
2、两对男女，分别优秀男1、一般男2；优秀女1、一般女2（“优秀”、“普通”方便理解，换成“青菜”、“萝卜”一个意思）
1.0、优秀女、男互相看中，普通女、男互相看中
- 女1喜欢：男1>男2
- 女2喜欢：男2>男1
- 男1喜欢：女1>女2
- 男2喜欢：女2>女1
- 结果：男1——女1、男2——女2分别匹配
- 解释：萝卜青菜各有所爱，分别各自找到自己最中意的
2.1.1、两女争优秀男，两男争优秀女
- 女1喜欢：男1>男2
- 女2喜欢：男1>男2
- 男1喜欢：女1>女2
- 男2喜欢：女1>女2
- 结果：优秀男1——优秀女1、一般男2——一般女2
- 解释：优者则优
2.2.1、两女争优秀男，两男争普通女
- 女1喜欢：男1>男2
- 女2喜欢：男1>男2
- 男1喜欢：女2>女1
- 男2喜欢：女2>女1
- 结果：优秀男1——普通女2、普通男2——优秀女1
- 解释：
- 两男争普通女，该普通女不普通，优先级高，是个“优秀女”，优秀男1同理，故两个被相争的在一起
- 该情况和上面一种“两女争优秀男，两男争优秀女”是类似
2.1.2、两女争普通男，两男争普通女：换身份，转换为“两女争优秀男，两男争优秀女”情况一样，
2.2.2、两女争普通男，两男争优质女：换身份，转换为“两女争优秀男，两男争普通女”情况一样
3.1.1、两女争优秀男，优秀男争优秀女、普通男争普通女
- 女1喜欢：男1>男2
- 女2喜欢：男1>男2
- 男1喜欢：女1>女2
- 男2喜欢：女2>女1
- 结果：优秀男1——优秀女1、一般男2——一般女2
- 解释：普通男1没被优秀女1优先选。
3.2.1、两女争优秀男，优秀男争普通女、普通男争优秀女
- 结果：优秀男1——普通女2、普通男2——优秀女1
- 解释：和3.1.1情况类似，优秀男权重更高（被两女相争）
3.1.2、两女争普通男，普通男争优秀女、优秀男争普通女
- 解释：和3.1.1情况类似，普通男、优秀男身份互换即可
3.2.2、两女争普通男，普通男争普通女、优秀男争优秀女
- 解释：和3.2.1情况类似，普通男、优秀男身份互换；
4、四角恋：女1->男1->女2->男2->女1
- 女1喜欢：男1>男2
- 女2喜欢：男2>男1
- 男1喜欢：女2>女1
- 男2喜欢：女1>女2
- 结果：
- 女士优先时：女1——男1、女2——男2
- 男士优先时：女2——男1、女1——男2
代码：
# coding:utf-8
"""
Demo of Gale-Shapley stable marriage algorithm.
Usage is:
python marriage.py [menfile] [womenfile]
or
python marriage.py [menfile] [womenfile] V
for verbose mode.
For simplicity, the file format is assumed (without checking) to match
the following format:
bob: alice,carol
david: carol,alice
and likewise for the womenfile, where there should be precisely same
number of men as with women, and the identifiers should be
self-consistent between the two files.
"""
import sys
# 原作者的例子:
womanChoices = '''
W: D,B,C,A
X: D,B,A,C
Y: A,D,B,C
Z: B,A,D,C
'''
manChoices = '''
A: W,X,Z,Y
B: W,Y,Z,X
C: X,W,Y,Z
D: W,Z,X,Y
'''
# 1.0、优秀女、男互相看中，普通女、男互相看中
womanChoices = '''
女1：男1，男2
女2：男2，男1
'''
manChoices = '''
男1：女1，女2
男2：女2，女1
'''
# 2.1.1、两优秀女争两优秀男、两优秀男争两优秀女
womanChoices = '''
女1：男1，男2
女2：男1，男2
'''
manChoices = '''
男1：女1，女2
男2：女1，女2
'''
# 3.1.1、两女争优秀男，优秀男争优秀女、普通男争普通女
womanChoices = '''
女1：男1，男2
女2：男1，男2
'''
manChoices = '''
男1：女1，女2
男2：女2，女1
'''
# 4、四角恋：女1->男1->女2->男2->女1
womanChoices = '''
女1：男1，男2
女2：男2，男1
'''
manChoices = '''
男1：女2，女1
男2：女1，女2
'''
# ---------------------------------------------------------------------------------------
# 现场活动男女们的选择：（格式类似上面的，一人一行，冒号、逗号注意）
# 女生
womanChoices = '''
'''
# 男生选择的结果：放这里
manChoices = '''
'''
# ---------------------------------------------------------------------------------------
class Person:
"""
Represent a generic person
"""
def __init__(self, name, priorities):
"""
name is a string which uniquely identifies this person
priorities is a list of strings which specifies a ranking of all
potential partners, from best to worst
"""
self.name = name
self.priorities = priorities
self.partner = None
def __repr__(self):
return 'Name is ' + self.name + 'n' +
'Partner is currently ' + str(self.partner) + 'n' +
'priority list is ' + str(self.priorities)
class Man(Person):
"""
Represents a man
"""
def __init__(self, name, priorities):
"""
name is a string which uniquely identifies this person
priorities is a list of strings which specifies a ranking of all
potential partners, from best to worst
"""
Person.__init__(self, name, priorities)
self.proposalIndex = 0 # next person in our list to whom we might propose
def nextProposal(self):
goal = self.priorities[self.proposalIndex]
self.proposalIndex += 1
return goal
def __repr__(self):
return Person.__repr__(self) + 'n' +
'next proposal would be to ' + self.priorities[self.proposalIndex]
class Woman(Person):
"""
Represents a woman
"""
def __init__(self, name, priorities):
"""
name is a string which uniquely identifies this person
priorities is a list of strings which specifies a ranking of all
potential partners, from best to worst
"""
Person.__init__(self, name, priorities)
# now compute a reverse lookup for efficient candidate rating
self.ranking = {}
for rank in range(len(priorities)):
self.ranking[priorities[rank]] = rank
def evaluateProposal(self, suitor):
"""
evaluates a proposal, though does not enact it.
suitor is the string identifier for the man who is proposing
returns True if proposal should be accepted, False otherwise
"""
return self.partner == None or self.ranking[suitor] < self.ranking[self.partner]
def parseFileOld(filename):
"""
Returns a list of (name,priority) pairs.
"""
people = []
f = file(filename)
for line in f:
pieces = line.split(':')
name = pieces[0].strip()
if name:
priorities = pieces[1].strip().split(',')
for i in range(len(priorities)):
priorities[i] = priorities[i].strip()
people.append((name, priorities))
f.close()
return people
def parseFile(choices):
choices = choices.replace('：', ':')
choices = choices.replace('，', ',')
people = []
for line in choices.split('n'):
pieces = line.split(':')
name = pieces[0].strip()
if name:
priorities = pieces[1].strip().split(',')
for i in range(len(priorities)):
priorities[i] = priorities[i].strip()
people.append((name, priorities))
return people
def printPairings(men):
for man in men.values():
print man.name, 'is paired with', str(man.partner)
def main_old():
verbose = len(sys.argv) > 3
# initialize dictionary of men
menlist = parseFile(sys.argv[1])
men = dict()
for person in menlist:
men[person[0]] = Man(person[0], person[1])
unwedMen = men.keys()
# initialize dictionary of women
womenlist = parseFile(sys.argv[2])
women = dict()
for person in womenlist:
women[person[0]] = Woman(person[0], person[1])
############################### the real algorithm ##################################
while unwedMen:
m = men[unwedMen[0]] # pick arbitrary unwed man
w = women[m.nextProposal()] # identify highest-rank woman to which
# m has not yet proposed
if verbose:
print m.name, 'proposes to', w.name
if w.evaluateProposal(m.name):
if verbose:
print ' ', w.name, 'accepts the proposal'
if w.partner:
# previous partner is getting dumped
mOld = men[w.partner]
mOld.partner = None
unwedMen.append(mOld.name)
unwedMen.remove(m.name)
w.partner = m.name
m.partner = w.name
else:
if verbose:
print ' ', w.name, 'rejects the proposal'
if verbose:
print "Tentative Pairings are as follows:"
printPairings(men)
print
# we should be done
print "Final Pairings are as follows:"
printPairings(men)
def main(manChoices, WomanChoices):
# initialize dictionary of men
menlist = parseFile(manChoices)
men = dict()
for person in menlist:
men[person[0]] = Man(person[0], person[1])
unwedMen = men.keys()
# initialize dictionary of women
womenlist = parseFile(WomanChoices)
women = dict()
for person in womenlist:
women[person[0]] = Woman(person[0], person[1])
############################### the real algorithm ##################################
while unwedMen:
m = men[unwedMen[0]] # pick arbitrary unwed man
w = women[m.nextProposal()] # identify highest-rank woman to which
# m has not yet proposed
if w.evaluateProposal(m.name):
if w.partner:
# previous partner is getting dumped
mOld = men[w.partner]
mOld.partner = None
unwedMen.append(mOld.name)
unwedMen.remove(m.name)
w.partner = m.name
m.partner = w.name
#####################################################################################
# we should be done
print "Final Pairings are as follows:"
printPairings(men)
if __name__ == "__main__":
# 女士优先，womanChoices放前面, 否则放后面
main(womanChoices, manChoices)
作者源代码：
- Gale-Shapley Stable Marriage Algorithm
参考资料：
- [算法]Gale-Shapley Algorithm-稳定匹配算法的设计、实现与探讨
- 算法 | 盖尔-沙普利(Gale-Shapley)婚姻稳定匹配算法
- Gale-Shapley算法（基于python3.6）
