Algorithm of the day -

The Gale-Shapley Algorithm

Summary

The Gale-Shapley algorithm is a solution to the Stable Marriage Problem, which is a classic problem in computer science and operations research. It is used to match two sets of entities, such as men and women, or students and colleges, in a stable and efficient manner.

Use Case

The Gale-Shapley algorithm has been used in real-world applications such as the National Resident Matching Program (NRMP) in the United States, which matches medical students with residency programs.

Steps

  1. First, each man proposes to his most preferred woman.
  2. Each woman then considers the proposals she has received and tentatively accepts the proposal from the man she prefers most.
  3. Each man who was rejected then proposes to his next most preferred woman.
  4. This process continues until all men have been accepted by a woman.
  5. Finally, the algorithm terminates and the stable marriages are formed.

Complexity

The time complexity of the Gale-Shapley algorithm is O(n^2), where n is the number of men or women. The space complexity is O(n), as we need to store the preferences of each man and woman.

Code Example

def gale_shapley(preferences_men, preferences_women):
    # Initialize the engagements
    engagements = {}
    free_men = list(preferences_men.keys())

    while free_men:
        man = free_men.pop(0)
        for woman in preferences_men[man]:
            if woman not in engagements.values():
                engagements[man] = woman
                break
            else:
                current_man = [k for k, v in engagements.items() if v == woman][0]
                if preferences_women[woman].index(man) < preferences_women[woman].index(current_man):
                    engagements[man] = woman
                    free_men.append(current_man)
                    break
    return engagements

# Example usage
preferences_men = {
    'A': ['W', 'X', 'Y', 'Z'],
    'B': ['X', 'W', 'Y', 'Z'],
    'C': ['Y', 'X', 'W', 'Z'],
    'D': ['Z', 'W', 'X', 'Y']
}
preferences_women = {
    'W': ['A', 'B', 'C', 'D'],
    'X': ['B', 'A', 'C', 'D'],
    'Y': ['C', 'A', 'B', 'D'],
    'Z': ['D', 'A', 'B', 'C']
}
print(gale_shapley(preferences_men, preferences_women))