Каждое Рождество мы рисуем имена для обмена подарками в моей семье. Обычно это связано с размытыми переливами, пока никто не вытащил их супруга. Итак, в этом году я закодировал собственное приложение для рисования имен, которое содержит кучу имен, кучу запрещенных пар и отправляет электронное письмо всем своим избранным giftee.
Сейчас алгоритм работает так (в псевдокоде):
function DrawNames(list allPeople, map disallowedPairs) returns map
// Make a list of potential candidates
foreach person in allPeople
person.potentialGiftees = People
person.potentialGiftees.Remove(person)
foreach pair in disallowedPairs
if pair.first = person
person.Remove(pair.second)
// Loop through everyone and draw names
while allPeople.count > 0
currentPerson = allPeople.findPersonWithLeastPotentialGiftees
giftee = pickRandomPersonFrom(currentPerson.potentialGiftees)
matches[currentPerson] = giftee
allPeople.Remove(currentPerson)
foreach person in allPeople
person.RemoveIfExists(giftee)
return matches
Кто-нибудь, кто знает больше о теории графов, знает какой-то алгоритм, который будет работать лучше здесь? Для моих целей это работает, но мне любопытно.
EDIT: Поскольку электронные письма давно вышли, и я просто надеюсь узнать что-то, я перефразирую это как вопрос теории графов. Меня не интересуют особые случаи, когда исключения - это все пары (как у супругов, не получающих друг друга). Меня больше интересуют случаи, когда есть достаточно исключений, что найти какое-либо решение становится трудной частью. Мой алгоритм выше - просто простой жадный алгоритм, который я не уверен, что это удастся во всех случаях.
Начиная с полного направленного графа и списка пар вершин. Для каждой пары вершин удалите ребро из первой вершины во вторую.
Цель состоит в том, чтобы получить граф, в котором каждая вершина имеет одно ребро, и одно ребро покидает.
