Gale-shapley算法的python实现

Gale-Shapley算法，也被称为稳定婚姻算法，是一种用于解决稳定婚姻匹配问题的算法。它的基本思想是通过迭代的方式，使得每个参与者都能够找到一个稳定的匹配。

在稳定婚姻匹配问题中，有两组参与者，比如男性和女性，每个参与者都有自己的偏好列表。算法的目标是找到一种匹配方式，使得不存在两个参与者，他们彼此更喜欢对方而不喜欢自己当前的匹配。

以下是Gale-Shapley算法的Python实现示例：

def gale_shapley(men_preferences, women_preferences):
    n = len(men_preferences)
    men_match = [-1] * n
    women_match = [-1] * n
    men_proposals = [0] * n

    while True:
        free_man = -1
        for i in range(n):
            if men_match[i] == -1:
                free_man = i
                break

        if free_man == -1:
            break

        woman = men_preferences[free_man][men_proposals[free_man]]
        men_proposals[free_man] += 1

        if women_match[woman] == -1:
            men_match[free_man] = woman
            women_match[woman] = free_man
        else:
            current_man = women_match[woman]
            if women_preferences[woman].index(current_man) > women_preferences[woman].index(free_man):
                men_match[free_man] = woman
                women_match[woman] = free_man
                men_match[current_man] = -1

    return men_match

# 示例使用
men_preferences = [[1, 0], [0, 1]]
women_preferences = [[0, 1], [1, 0]]
result = gale_shapley(men_preferences, women_preferences)
print(result)

上述代码实现了Gale-Shapley算法，其中men_preferences和women_preferences分别表示男性和女性的偏好列表。算法返回一个列表，表示每个男性最终匹配的女性。

Gale-Shapley算法的应用场景包括稳定婚姻匹配、任务分配等。在云计算领域，该算法可以用于资源分配和负载均衡等问题。

腾讯云相关产品和产品介绍链接地址：