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:
- Attraction is symmetric; i.e. if person
Ais attracted to person
B, then person
Bis attracted to person
- Attraction is antitransitive; i.e. if person
Bare each attracted to person
C, then person
Bare 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
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.
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 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 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.