python舞伴问题

舞伴问题是一个稳定匹配问题，也被称为Gale-Shapley算法。它是一个经典的算法，用于解决两组人之间的配对问题，其中每个人都有自己的偏好列表。算法的目标是找到一个稳定的匹配，即不存在任何一对人，他们更喜欢彼此而不是他们当前的配对。

以下是一个用Python演示舞伴问题的例子：

def stable_matching(men, women):
    # 创建一个字典，用于存储每个人的当前配对
    engaged = {}
    # 创建一个字典，用于存储每个人的偏好列表
    preferences = {}
    # 创建一个队列，用于存储未匹配的男性
    free_men = []

    # 初始化未匹配的男性队列和偏好列表
    for man in men:
        free_men.append(man)
        preferences[man] = women[man]

    # 开始匹配过程
    while free_men:
        man = free_men[0]
        woman = preferences[man][0]

        # 如果女性没有配对，直接匹配
        if woman not in engaged:
            engaged[woman] = man
            free_men.pop(0)
        else:
            current_man = engaged[woman]
            # 如果女性更喜欢当前的配对，继续匹配下一个男性
            if preferences[woman].index(man) < preferences[woman].index(current_man):
                free_men.pop(0)
                free_men.append(current_man)
                engaged[woman] = man

        # 更新男性的偏好列表
        preferences[man] = preferences[man][1:]

    return engaged

men = ['Tom', 'John', 'Mike']
women = {'Tom': ['Mary', 'Jane', 'Lisa'],
         'John': ['Jane', 'Mary', 'Lisa'],
         'Mike': ['Lisa', 'Mary', 'Jane']}

result = stable_matching(men, women)
print(result)

输出结果为：

{'Mary': 'Tom', 'Jane': 'John', 'Lisa': 'Mike'}

这表示Mary与Tom匹配，Jane与John匹配，Lisa与Mike匹配。