Stabiles Eheproblem

Hintergrund

Angenommen, es gibt 2*nMenschen, die verheiratet werden müssen, und es wird weiterhin angenommen, dass sich jede Person von genau nanderen Menschen unter den folgenden Bedingungen angezogen fühlt :

1. Anziehung ist symmetrisch ; dh wenn eine Person Avon einer Person angezogen wird, wird eine Person von einer BPerson Bangezogen A.
2. Anziehung ist antitransitiv ; dh wenn sich Person Aund Person Bjeweils zu Person hingezogen fühlen C, dann fühlen sich Person Aund Person Bnicht zueinander hingezogen.

Das Netzwerk der Attraktionen bildet somit den (ungerichteten) vollständigen zweigliedrigen Graphen Kn,n . Wir gehen auch davon aus, dass jede Person die Personen eingestuft hat, zu denen sie hingezogen sind. Diese können im Diagramm als Kantengewichte dargestellt werden.

Eine Ehe ist eine Paarung, (A,B)in der Aund Bvon einander angezogen werden. Die Ehe ist instabil, wenn es eine andere Ehe gibt, in der eine Person aus jeder Ehe ihren Partner scheiden und sich heiraten könnte und beide mit jemandem enden, den sie höher eingestuft haben als ihr früherer Partner.

Tor

Ihre Aufgabe ist es, ein komplettes Programm oder eine Funktion zu schreiben, die die Vorlieben jeder Person als Eingabe verwendet und eine Ehe für jede Person ausgibt, so dass jede Ehe stabil ist.

Eingang

Die Eingabe kann in einem beliebigen Format erfolgen. Beispiel: gewichteter Graph, geordnete Präferenzliste, Wörterbuch / Zuordnung usw. Sie können optional die Gesamtzahl der Personen als Eingabe verwenden, aber keine andere Eingabe ist zulässig.

Ausgabe

Die Ausgabe kann auch in einem beliebigen Format erfolgen. zB Liste der Tupel, minimale Randbedeckung , eine Funktion, die jeder Person ihren Partner zuordnet usw. Beachten Sie, dass die einzige Einschränkung darin besteht, dass jede Ehe stabil ist und es keine anderen Optimalitätsanforderungen gibt.

Anmerkungen

1. Weitere Informationen und einen O(n^2)Algorithmus zur Lösung dieses Problems finden Sie auf Wikipedia oder in diesem Numberphile-Video . Es steht Ihnen jedoch frei, einen beliebigen Algorithmus zu verwenden.
2. Standardlücken sind verboten.
3. Das ist Code-Golf . Kürzeste Antwort (in Bytes) gewinnt.

Mathematica, 28 Bytes

Ich würde denken, das ist Betrug. Ich für mich selbst mag das:

Combinatorica`StableMarriage

• Muss mit den Gewichtsmatrizen der Vorlieben für Männer und Frauen aufgerufen werden.
• Gibt die Direktindizes für die Kopplung zurück.

(Ja Combinatoricaist veraltet, kostet aber weniger Bytes als FindIndependentEdgeSet)

Beispiel (GoT-like): (Um fair zu sein - ich habe die Gewichte erraten ... aber ich bin in Ordnung mit den Ergebnissen)

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