# Stable marriage problem

## Background

Suppose that there are 2*n people to be married, and suppose further that each person is attracted to exactly n other people under the constraints that:

1. Attraction is symmetric; i.e. if person A is attracted to person B, then person B is attracted to person A.
2. Attraction is antitransitive; i.e. if person A and person B are each attracted to person C, then person A and person B are not attracted to each other.

Thus the network of attractions forms the (undirected) complete bipartite graph Kn,n. We also assume that each person has ranked the people they are attracted to. These may be represented as edge weights in the graph.

A marriage is a pairing (A,B) where A and B are attracted to each other. The marriage is unstable if there is another marriage where one person from each marriage could divorce their partner and marry each other and both end up with someone they ranked higher than their former partner.

## Goal

Your task is to write a complete program or function which takes each person's preferences as input and outputs a marriage for each person such that each marriage is stable.

## Input

Input may be in any convenient format; e.g., weighted graph, ordered list of preferences, dictionary/assocation, etc. You may optionally take the total number of people as input, but no other input is allowed.

## Output

Output can also be in any convenient format; e.g. list of tuples, minimal edge cover, a function which associates to each person their partner, etc. Note that the only constraint is that each marriage is stable, there are no other optimality requirements.

## Notes

1. You can find more information and an O(n^2) algorithm to solve this problem on Wikipedia or this Numberphile video. You are free to use any algorithm, however.
2. Standard loopholes are forbidden.
3. This is . Shortest answer (in bytes) wins.
• Attraction is symmetric Ha! Feb 13, 2017 at 22:11
• @LuisMendo I'm continuing in the storied tradition of unrealistic word problems :)
– user61980
Feb 13, 2017 at 22:18
• It's Valentine's day tho (UTC+8 here) Feb 14, 2017 at 13:24

## Mathematica, 28 bytes

On would think, this is cheating. I for myself like this:

CombinatoricaStableMarriage

• Needs to be called with the weight matrices of the preferences for men and women.
• Returns the direct indizes for the coupling.

(Yes Combinatorica is deprecated but it costs fewer bytes than FindIndependentEdgeSet)

Example (GoT-like): (To be fair - i guessed the weights...but i'm okay with the results)

m = {{2, 4, 3, 1}, {1, 2, 4, 3}, {3, 2, 1, 4}, {4, 2, 1, 3}};
w = {{2, 3, 4, 1}, {3, 2, 1, 4}, {3, 2, 4, 1}, {4, 1, 2, 3}};
result = CombinatoricaStableMarriage[w, m];