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\$
  • 15
    \$\begingroup\$ Attraction is symmetric Ha! \$\endgroup\$ – Luis Mendo Feb 13 '17 at 22:11
  • 5
    \$\begingroup\$ @LuisMendo I'm continuing in the storied tradition of unrealistic word problems :) \$\endgroup\$ – ngenisis Feb 13 '17 at 22:18
  • 2
    \$\begingroup\$ It's Valentine's day tho (UTC+8 here) \$\endgroup\$ – busukxuan Feb 14 '17 at 13:24
7
\$\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
    \$\begingroup\$ +1 for exploiting Mathematica's epic library of useless-to-everyone-except-code-golfers functions. \$\endgroup\$ – SIGSTACKFAULT Feb 14 '17 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\$ – ngenisis Feb 14 '17 at 23:01
  • \$\begingroup\$ Never underestimate Mathematicas built-ins ;D \$\endgroup\$ – Julien Kluge Feb 15 '17 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.