Стабильная проблема брака

Фон

Предположим, что есть 2*nлюди, которые должны состоять в браке, и далее предположим, что каждый человек привлекается именно к nдругим людям в соответствии с ограничениями, которые:

1. Аттракцион симметричный ; то есть, если человек Aпривязан к человеку B, то человек Bпривязан к человеку A.
2. Аттракцион антитранзитивен ; то есть, если человек Aи человек Bпривлечены к человеку C, то человек Aи человек Bне привлечены друг к другу.

Таким образом, сеть аттракционов образует (ненаправленный) полный двудольный граф Kn,n . Мы также предполагаем, что каждый человек оценил людей, которых он привлекает. Они могут быть представлены как граничные веса на графике.

Брак спаривание , (A,B)где Aи Bпритягиваются друг к другу. Брак нестабилен, если есть другой брак, где один человек от каждого брака может развестись со своим партнером и жениться друг на друге, и оба в конечном итоге с кем-то, кого они оценили выше, чем их бывший партнер.

Цель

Ваша задача - написать полную программу или функцию, которая принимает предпочтения каждого человека в качестве входных данных и выводит брак для каждого человека таким образом, чтобы каждый брак был стабильным.

вход

Ввод может быть в любом удобном формате; например, взвешенный график, упорядоченный список предпочтений, словарь / ассоциация и т. д. Вы можете по желанию принять общее количество людей в качестве входных данных, но другие входные данные не допускаются.

Выход

Вывод также может быть в любом удобном формате; например, список кортежей, минимальное покрытие , функция, которая связывает каждого человека с его партнером и т. д. Обратите внимание, что единственным ограничением является то, что каждый брак стабилен, других требований к оптимальности нет.

Примечания

1. Вы можете найти больше информации и O(n^2)алгоритм для решения этой проблемы в Википедии или в этом видео Numberphile . Вы можете использовать любой алгоритм, однако.
2. Стандартные лазейки запрещены.
3. Это код-гольф . Кратчайший ответ (в байтах) выигрывает.

Mathematica, 28 байт

По-моему, это обман. Мне для себя это нравится

Combinatorica`StableMarriage

• Необходимо назвать с весами матрицы предпочтений для мужчин и женщин.
• Возвращает прямые индексы для муфты.

(Да Combinatoricaне рекомендуется, но стоит меньше байтов, чем FindIndependentEdgeSet)

Пример (GoT-like): (Чтобы быть справедливым - я угадал вес ... но я в порядке с результатами)

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