稳定匹配-stablematching(代码片段)

# -*- encoding: UTF-8 -*-
import copy
 
 
# 男的所期望的对象
manPrefers = dict((m, prefs.split(‘, ‘)) for [m, prefs] in (line.rstrip().split(‘: ‘)
                                for line in open(‘men.txt‘)))
# 女的所期望的对象
womenPrefers = dict((m, prefs.split(‘, ‘)) for [m, prefs] in (line.rstrip().split(‘: ‘)
                                for line in open(‘women.txt‘)))
 
men = sorted(manPrefers.keys())
women = sorted(womenPrefers.keys())

# 定义检测函数检测匹配的伴侣是否稳定
def check(engaged):
    inverseengaged = dict((v,k) for k,v in engaged.items())
    for w, m in engaged.items():
        shelikes = womenPrefers[w]
        shelikesbetter = shelikes[:shelikes.index(m)]
        helikes = manPrefers[m]
        helikesbetter = helikes[:helikes.index(w)]
        for man in shelikesbetter:
            womenOftheMan = inverseengaged[man]
            manLoves = manPrefers[man]
            if manLoves.index(womenOftheMan) > manLoves.index(w):
                print("%s 和 %s 更喜欢彼此相比起他们当前的伴侣: %s 和 %s" % (w, man, m, womenOftheMan))
                return False
        for woman in helikesbetter:
            manOfTheWomen = engaged[woman]
            womanLoves = womenPrefers[woman]
            if womanLoves.index(manOfTheWomen) > womanLoves.index(m):
                print("%s 和 %s 更喜欢彼此相比起他们当前的伙伴：%s 和 %s" % (m, woman, w, manOfTheWomen))
                return False
    return True
 
def stableMatching():
    free_men = men[:]
    engaged  = 
    manPref_temp = copy.deepcopy(manPrefers)
    womenPref_temp = copy.deepcopy(womenPrefers)
    while free_men:
        man = free_men.pop(0)
        manList = manPref_temp[man]
        woman = manList.pop(0)
        fiance = engaged.get(woman)
        if not fiance:
            engaged[woman] = man
            print("  %s 和 %s 成为伴侣" % (man, woman))
        else:
            womenList = womenPref_temp[woman]
            if womenList.index(fiance) > womenList.index(man):
                engaged[woman] = man
                print("  %s 舍弃 %s 而和 %s 成为伴侣" % (woman, fiance, man))
                if manPref_temp[fiance]:
                    free_men.append(fiance)
            else:
                if manList:
                    free_men.append(man)
    return engaged
 
if __name__ == ‘__main__‘:
    print(‘
伴侣匹配:‘)
    engaged = stableMatching()
 
    print(‘
伴侣匹配:‘)
    print(‘  ‘ + ‘,
  ‘.join(‘%s 和 %s 成为伴侣‘ % couple for couple in sorted(engaged.items())))
    print()
    print(‘伴侣稳定性检测通过‘ if check(engaged) else ‘伴侣稳定性检测不通过‘)
 
    print(‘

因交换而产生伴侣搭配错误‘)
    engaged[women[0]], engaged[women[1]] = engaged[women[1]], engaged[women[0]]
    for woman in women[:2]:
        print(‘  %s 现在和 %s 成为伴侣‘ % (woman, engaged[woman]))
    print()
    print(‘伴侣稳定性检测通过‘ if check(engaged) else ‘伴侣稳定性检测不通过‘)