我想用Python编写Gale-Shapely算法,以处理不平等的配对数(即男性多于女性或女性多于男性)。结果应该是相同数量的稳定配对,不匹配的剩余部分将被忽略。目前我的实现方式适用于女性人数大于男性人数的情况,但如果男性人数大于女性人数,则会产生无限循环,因为'freeMen'列表永远不为空,而while循环将无限迭代。我正在努力找出如何正确实现它的方法。下面是代码,其中第一个列表参数包括每个男人的键和按顺序排列的优先女性值,第二个列表参数相反:
def gale_shapely_matching(men_preferences, woman_preferences):
#create array to store the tempory pairings whilst iterating through matchings
temporyMatches = []
#create list of the free men
freeMen = [user for user in list(men_preferences.keys())]
#while loop to iterate while the freeMen array is not empty
while len(freeMen)>0:
for man in freeMen:
for woman in men_preferences[man]:
takenMatch = [match for match in temporyMatches if woman in match]
if takenMatch:
current_match = woman_preferences[woman].index(takenMatch[0][0])
potential_new_match = woman_preferences[woman].index(man)
#check if the the potential new matched man ranks higher in the womans preference (is a lower index). If man is higher preference amend match so as new man replaces previous match
if potential_new_match < current_match:
freeMen.remove(man)
freeMen.append(takenMatch[0][0])
takenMatch[0][0] = man
break
else:
pass
else:
temporyMatches.append([man, woman])
freeMen.remove(man)
break
return temporyMatches
非常感谢任何能够帮助的人。