Алгоритм для лучшего соответствия выборам людей из определенного списка предметов, где есть только один из доступных?

Question

Дамы и господа,

Мои лучшие друзья и я каждый год проводим обмен подарками типа «Секретный Санта», в этом году я пытался придумать несколько способов сделать его интересным. В нем участвуют шесть человек, и я хочу разработать небольшую программу, которая позволит шестерым из нас оценить предпочтительных получателей подарков от 1 до 5, а также предпочитаемых дарителей.

Итак, допустим, нас называют A, B, C, D, E и F.

A представляет два списка:

Список 1 - Люди, которым я больше всего хотел бы сделать подарок: B, D, C, F, E

Список 2 - Люди, от которых мне больше всего хотелось бы получить подарок: F, D, E, B, C

Все шестеро из нас представят оба этих списка, поэтому у меня будет 12 списков вместе. Полагаю, мой вопрос в том, каков наилучший алгоритм, позволяющий теперь назначать каждому человеку получателя подарка?

Я думал о чем-то вроде этого:

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

После того, как я назначил "идеальные совпадения", я все-таки потерялся, есть ли алгоритм установления для подобных ситуаций? Очевидно, что это только для развлекательной ценности, но наверняка должно быть «реальное» применение чего-то подобного? Возможно расписание или что-то?

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

Cheers, (и счастливых праздников, я думаю), Rob

---

Обновление / Часть 2

Хорошо, Ин Сяо пришел на помощь, порекомендовав алгоритм Гейли Шепли для Устойчивой проблемы брака , и я реализовал это в Python и его работает угощение Тем не менее, это просто мысль, которая пришла мне в голову. Я предполагаю, что в нашей группе из шести лучших друзей есть три пары «экстра-лучших» друзей, поэтому у меня есть ощущение, что мы просто получим три пары AB, CD, EF и BA, DC, FE с точки зрения подарка давать и получать.

Есть ли алгоритм, который мы могли бы разработать, который учитывал бы ранжирование людей, но также ограничивал двух людей, образующих "закрытую группу"? То есть, если А назначено купить подарок для Б, B нельзя назначить купить подарок для А? Возможно, мне нужно решить проблему Стабильные соседи по комнате ?

Похожие вопросы:

• Секретный алгоритм Санты.
• Каков лучший низкотехнологичный протокол для имитации рисования имен из шляпы и обеспечения секретности?

Answer 1

Алгоритм Гейла-Шепли (для задачи «Устойчивый брак») применяется только в том случае, если у каждого человека есть ранжированный список всех других участников - вы можете или не сможете преобразовать свою проблему в эту форму (сделать каждого рангом все ).

Кроме того, обратите внимание, что то, для чего он оптимизируется, является чем-то другим: он пытается найти набор стабильных браков , где ни одна пара людей не «сбежит», потому что они предпочитают друг друга своим нынешним партнеры. Это не то, что вас волнует в вашем приложении Secret Santa.

То, что вы хотите (в зависимости от вашего определения «лучший»), - это согласование по максимальному весу , которое устраняет оба вышеупомянутых возражения: поставьте «дающих» с одной стороны, «получателей» с другой стороны (в данном случае две копии каждого человека) присвойте каждому ребру вес, соответствующий тому, насколько высоко этот даритель оценивает этого получателя, и теперь это проблема назначения . Для этого вы можете использовать Венгерский алгоритм или более простые (более медленные). Вы также можете изменить способ назначения весов для оптимизации для разных вещей (например, максимизировать количество людей, которые получают первый выбор, или свести к минимуму худший выбор, который кто-либо получает, и т. Д.)

Если вы используете алгоритм стабильного брака Гейла-Шепли, обратите внимание, что он является оптимальным для "предлагающих" (мужчина-оптимальный и женский-пессимальный), поэтому не забудьте указать "дающих" в качестве "предлагающих", а не наоборот.

Answer 2

Для каждого человека создайте двух виртуальных людей: «даритель» и «получатель». Теперь сопоставьте набор дающих с набором получателей, используя алгоритм Гейла Шепли. Работает за O (n ^ 2) раз.

http://en.wikipedia.org/wiki/Stable_marriage_problem