Stabilny problem małżeński

tło

Załóżmy, że są 2*nludzie do zawarcia małżeństwa, i przypuśćmy ponadto, że każda osoba jest pociągana do dokładnie ninnych osób pod ograniczeniami, które:

1. Przyciąganie jest symetryczne ; tzn. jeśli dana osoba Ajest pociągana do osoby B, to osoba Bjest pociągana do osoby A.
2. Przyciąganie jest nieprzechodnie ; tj. jeśli osoba Ai osoba Bsą przyciągane do siebie C, wówczas osoba Ai osoba Bnie są przyciągane do siebie.

W ten sposób sieć atrakcji tworzy (nieukierowany) kompletny dwustronny wykres Kn,n . Zakładamy również, że każda osoba uszeregowała osoby, które ich pociągają. Mogą być one przedstawione na wykresie jako grubości krawędzi.

Małżeństwo jest parowanie (A,B)gdzie Ai Bprzyciąga do siebie. Małżeństwo jest niestabilne, jeśli istnieje inne małżeństwo, w którym jedna osoba z każdego małżeństwa mogłaby rozwieść się ze swoim partnerem i poślubić się nawzajem oraz oboje skończyć z kimś, którego zajęli wyżej niż dawny partner.

Cel

Twoim zadaniem jest napisanie pełnego programu lub funkcji, które przyjmują preferencje każdej osoby jako dane wejściowe i generują małżeństwo dla każdej osoby, tak aby każde małżeństwo było stabilne.

Wejście

Dane wejściowe mogą być w dowolnym dogodnym formacie; np. wykres ważony, uporządkowana lista preferencji, słownik / przypisanie itp. Opcjonalnie możesz wziąć całkowitą liczbę osób jako dane wejściowe, ale żadne inne dane nie są dozwolone.

Wynik

Dane wyjściowe mogą być również w dowolnym dogodnym formacie; np. lista krotek, minimalne pokrycie krawędzi , funkcja, która kojarzy się każdej osobie z partnerem, itd. Należy pamiętać, że jedynym ograniczeniem jest to, że każde małżeństwo jest stabilne, nie ma innych wymagań dotyczących optymalności.

Notatki

1. Możesz znaleźć więcej informacji i O(n^2)algorytm, aby rozwiązać ten problem na Wikipedii lub w tym filmie Numberphile . Możesz jednak użyć dowolnego algorytmu.
2. Standardowe luki są zabronione.
3. To jest golf golfowy . Najkrótsza odpowiedź (w bajtach) wygrywa.

Mathematica, 28 bajtów

Myślę, że to oszustwo. Ja dla siebie lubię to:

Combinatorica`StableMarriage

• Trzeba nazywać go macierzami preferencji dla mężczyzn i kobiet.
• Zwraca bezpośrednie indeksy dla sprzężenia.

(Tak, Combinatoricajest przestarzałe, ale kosztuje mniej bajtów niż FindIndependentEdgeSet)

Przykład (podobny do GoT): (Szczerze mówiąc - odgadłem wagi ... ale nie mam nic przeciwko wynikom)

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