Существует ли какой-либо код Python или модификация алгоритма Гейла Шепли, чтобы он мог решить проблему стабильного брака с неполными списками предпочтений

Question

У меня немного другая формулировка проблемы стабильного брака. По сути, я могу сопоставить одного мужчину с одной женщиной, но список предпочтений неполный, что означает, что мужчина проявил интерес только к подмножеству женщин и наоборот. Я не думаю, что оригинальный алгоритм Гейла Шепли подойдет для этого, если да, то какие модификации мне нужно сделать? Если Гейл Шейпли здесь не работает, есть ли алгоритм для решения этой проблемы? предложения по коду, особенно в python для такого рода проблем, очень приветствуются.

Если говорить более конкретно, это проблема:

Men = [1, 2, 3, 4, 5]
Women = [a, b, c, d, e]

предпочтения:

мужчины:

1: a, c, d
2: d, a, b
3: a, e, b
4: c, a, d
5: e, d, a

женщин:

a: 1, 3, 4
b: 4, 2, 5
c: 5, 1, 4
d: 3, 2, 1
e: 5, 3, 1

Мне нужно сопоставить каждого мужчину с одной и только одной женщиной, и количество разрешенных предпочтений фиксировано и меньше количества кандидатов.

Answer 1

Вам нужно как-то определить весь список предпочтений, иначе алгоритм не будет работать. Тем не менее, должно быть относительно просто «заполнить» список предпочтений оставшимися мужчинами / женщинами произвольно; Вы можете назначить статический порядок или назначить эти параметры случайным образом.

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

Что касается подходов Python, есть несколько способов сделать это; в основном это будет зависеть от того, как вы пытаетесь подойти к реализации алгоритма.