Solving the Stable Marriage problem with Erlang by Yan Cui.
With all the Ashley Madison hack publicity, I didn’t know there was a “stable marriage problem.” 😉
Turns out is it like the Eight-Queens problem. Is is a “problem” but it isn’t one you are likely to encounter outside of a CS textbook.
Yan sets up the problem with this quote from Wikipedia:
The stable marriage problem is commonly stated as:
Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable”. (It is assumed that the participants are binary gendered and that marriages are not same-sex).
The wording is a bit awkward. I would rephrase it to say that for no pair, both partners prefer some other partner. One of the partner’s can prefer someone else, but if the someone else does not share that preference, both marriages are “stable.”
The Wikipedia article does observe:
While the solution is stable, it is not necessarily optimal from all individuals’ points of view.
Yan sets up the problem and then walks through the required code.
Enjoy!