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)