Problème de mariage stable

Contexte

Supposons qu'il y ait des 2*npersonnes à marier et supposons en outre que chaque personne soit attirée par exactement d' nautres personnes sous les contraintes suivantes:

1. L'attraction est symétrique ; c'est-à-dire que si la personne Aest attirée par la personne B, alors la personne Best attirée par la personne A.
2. L'attraction est antitransitive ; c'est-à-dire que si la personne Aet la personne Bsont chacune attirées par la personne C, alors la personne Aet la personne Bne sont pas attirées l'une par l'autre.

Ainsi, le réseau d'attractions forme le graphe bipartite complet (non dirigé) Kn,n. Nous supposons également que chaque personne a classé les personnes qu'elle attire. Ceux-ci peuvent être représentés comme des poids de bord dans le graphique.

Un mariage est un couple (A,B)où Aet Bsont attirés les uns aux autres. Le mariage est instable s'il y a un autre mariage où une personne de chaque mariage pourrait divorcer de son partenaire et se marier et se retrouver avec une personne de rang supérieur à leur ancien partenaire.

Objectif

Votre tâche consiste à écrire un programme ou une fonction complète qui prend en compte les préférences de chaque personne et génère un mariage pour chaque personne de sorte que chaque mariage soit stable.

Contribution

L'entrée peut être dans n'importe quel format pratique; par exemple, graphique pondéré, liste ordonnée de préférences, dictionnaire / association, etc. Vous pouvez éventuellement prendre le nombre total de personnes en entrée, mais aucune autre entrée n'est autorisée.

Production

La sortie peut également être dans n'importe quel format pratique; par exemple liste de tuples, couverture minimale des bords , une fonction qui associe à chaque personne son partenaire, etc. Notez que la seule contrainte est que chaque mariage est stable, il n'y a pas d'autre exigence d'optimalité.

Remarques

1. Vous pouvez trouver plus d'informations et un O(n^2)algorithme pour résoudre ce problème sur Wikipedia ou cette vidéo Numberphile . Vous êtes cependant libre d'utiliser n'importe quel algorithme.
2. Les failles standard sont interdites.
3. C'est du code-golf . La réponse la plus courte (en octets) l'emporte.

Mathematica, 28 octets

On pourrait penser que c'est de la triche. Pour moi comme ça:

Combinatorica`StableMarriage

• Doit être appelé avec les matrices de poids des préférences pour les hommes et les femmes.
• Renvoie les index directs pour le couplage.

(Oui Combinatoricaest déconseillé mais il coûte moins d'octets que FindIndependentEdgeSet)

Exemple (GoT-like): (Pour être juste - j'ai deviné les poids ... mais je suis d'accord avec les résultats)

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