Gale Shapley Stable Marriage Algorithm

Implementation of the Gale-Shapley stable matching algorithm.

Given N men and N women, and the preferences of each of them over the members of the opposite gender, a stable matching is a matching between the N men and women such that there is no man and woman who prefer each other over their respectively matched partners.

The Gale-Shapley algorithm determines such a stable matching. Depending on the formulation, it provides either a men-optimal or a women-optimal stable matching. The given function determines the men-optimal stable matching. One can determine the women-optimal stable matching by switching the preferences in the input. An example is provided.