12
\$\begingroup\$

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.
\$\endgroup\$
3
  • 15
    \$\begingroup\$ Attraction is symmetric Ha! \$\endgroup\$
    – Luis Mendo
    Feb 13, 2017 at 22:11
  • 5
    \$\begingroup\$ @LuisMendo I'm continuing in the storied tradition of unrealistic word problems :) \$\endgroup\$
    – user61980
    Feb 13, 2017 at 22:18
  • 2
    \$\begingroup\$ It's Valentine's day tho (UTC+8 here) \$\endgroup\$
    – busukxuan
    Feb 14, 2017 at 13:24

1 Answer 1

8
\$\begingroup\$

Mathematica, 28 bytes

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

Combinatorica`StableMarriage
  • 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)

enter image description here

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 = Combinatorica`StableMarriage[w, m];
MapThread[
  UndirectedEdge[Show[#1, ImageSize -> 130], 
    Show[#2, ImageSize -> 130]] &, {names1, 
   names2[[result]]}] // TableForm

Blockquote

\$\endgroup\$
3
  • 3
    \$\begingroup\$ +1 for exploiting Mathematica's epic library of useless-to-everyone-except-code-golfers functions. \$\endgroup\$ Feb 14, 2017 at 17:41
  • 2
    \$\begingroup\$ I need to get in the habit of disallowing built-ins even when I'm confident that one doesn't exist :) \$\endgroup\$
    – user61980
    Feb 14, 2017 at 23:01
  • \$\begingroup\$ Never underestimate Mathematicas built-ins ;D \$\endgroup\$ Feb 15, 2017 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.