Алгоритм тайного Санты
https://stackoverflow.com/questions/273567
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Каждое Рождество в моей семье мы рисуем названия для обмена подарками.Обычно это включает в себя многократную перерисовку до тех пор, пока никто не вытащит своего супруга.Итак, в этом году я закодировал свое собственное приложение для рисования имен, которое набирает кучу имен, кучу запрещенных пар и отправляет всем электронное письмо с выбранным подарком.
Прямо сейчас алгоритм работает следующим образом (в псевдокоде)::
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
Кто-нибудь, кто больше разбирается в теории графов, знает какой-нибудь алгоритм, который работал бы здесь лучше?Для моих целей это работает, но мне любопытно.
Редактировать:Поскольку электронные письма были отправлены некоторое время назад, и я просто надеюсь чему-нибудь научиться, я перефразирую это как вопрос теории графов.Меня не очень интересуют особые случаи, когда исключениями являются все пары (например, когда супруги не понимают друг друга).Меня больше интересуют случаи, когда существует достаточное количество исключений, из-за которых поиск любого решения становится сложной частью.Мой приведенный выше алгоритм - это всего лишь простой жадный алгоритм, который, я не уверен, будет успешным во всех случаях.
Начиная с полного ориентированного графа и списка пар вершин.Для каждой пары вершин удалите ребро из первой вершины во вторую.
Цель состоит в том, чтобы получить график, в котором каждая вершина имеет одно входящее ребро и одно выходящее.
Решение
Просто создайте график с ребрами, соединяющими двух людей, если им разрешено делиться подарками, а затем используйте алгоритм идеального соответствия. (Ищите «Пути, деревья и цветы» для (умного) алгоритма)
Другие советы
Я бы не стал использовать запрещенные пары, поскольку это значительно усложняет задачу. Просто введите имя и адрес каждого в список. Создайте копию списка и продолжайте перетасовывать ее, пока адреса в каждой позиции двух списков не совпадут. Это гарантирует, что никто не получит себя или своего супруга.
В качестве бонуса, если вы хотите использовать этот стиль тайного голосования, печатайте конверты из первого списка и имена из второго списка. Не заглядывайте, когда набиваете конверты. (Или вы можете просто автоматизировать рассылку по электронной почте всем, кого выбираете.)
Существует еще больше решений этой проблемы в этой темы .
Я просто делал это сам, в конце концов, алгоритм, который я использовал, точно не моделирует рисование имен из шляпы, но это чертовски близко. В основном перемешайте список, а затем соедините каждого человека со следующим человеком в списке. Единственная разница с рисованием имен из шляпы состоит в том, что вы получаете один цикл вместо того, чтобы потенциально получить мини-подгруппы людей, которые только обмениваются подарками друг с другом. Во всяком случае, это может быть функцией.
Реализация на Python:
import random
from collections import deque
def pairup(people):
""" Given a list of people, assign each one a secret santa partner
from the list and return the pairings as a dict. Implemented to always
create a perfect cycle"""
random.shuffle(people)
partners = deque(people)
partners.rotate()
return dict(zip(people,partners))
Хммм.Я прослушал курс теории графов, но проще всего просто случайным образом переставить свой список, соединить каждую последовательную группу, а затем поменять любой запрещенный элемент другим.Поскольку ни в одной данной паре нет запрещенного участника, обмен всегда будет успешным, если вы не разрешите обмен с выбранной группой.Ваш алгоритм слишком сложен.
Создайте график, в котором каждое ребро имеет «giftability». Вершины, представляющие супругов, НЕ будут смежными. Выберите ребро наугад (это подарок). Удалите все ребра, идущие от подарка, и все ребра, идущие к приемнику, и повторите.
В теории графов существует понятие, называемое гамильтонова схема , которое описывает " цель " Вы описываете. Одним из советов для тех, кто обнаружит это, является информирование пользователей о том, что «семя» был использован для генерации графика. Таким образом, если вам нужно заново сгенерировать график, вы можете. «Семя» также полезно, если вам нужно добавить или удалить человека. В этом случае просто выберите новое «семя» и сгенерируйте новый график, убедившись в том, что он сообщит участникам, кто "затравил" текущий / последний.
Здесь простая реализация в Java для секретной проблемы Санты.
public static void main(String[] args) {
ArrayList<String> donor = new ArrayList<String>();
donor.add("Micha");
donor.add("Christoph");
donor.add("Benj");
donor.add("Andi");
donor.add("Test");
ArrayList<String> receiver = (ArrayList<String>) donor.clone();
Collections.shuffle(donor);
for (int i = 0; i < donor.size(); i++) {
Collections.shuffle(receiver);
int target = 0;
if(receiver.get(target).equals(donor.get(i))){
target++;
}
System.out.println(donor.get(i) + " => " + receiver.get(target));
receiver.remove(receiver.get(target));
}
}
Решение Python здесь.
Учитывая последовательность (персона, теги) , где теги сами по себе являются (возможно, пустой) последовательностью строк, мой алгоритм предлагает цепочку людей, где каждый человек дает подарок следующему в цепь (последний человек, очевидно, в паре с первым).
Теги существуют для того, чтобы лица могли быть сгруппированы, и каждый раз, когда следующий человек выбирается из группы, которая наиболее разобщена с последним выбранным человеком. Первоначальный человек выбирается пустым набором тегов, поэтому он будет выбран из самой длинной группы.
Итак, учитывая последовательность ввода:
example_sequence= [
("person1", ("male", "company1")),
("person2", ("female", "company2")),
("person3", ("male", "company1")),
("husband1", ("male", "company2", "marriage1")),
("wife1", ("female", "company1", "marriage1")),
("husband2", ("male", "company3", "marriage2")),
("wife2", ("female", "company2", "marriage2")),
]
предложение:
['person1 [мужчина, компания1]', 'person2 [женщина, компания2]', 'person3 [мужчина, компания1]', 'жена2 [женщина, брак2, компания2]', 'Муж1 [мужчина, брак1, компания2]', 'Муж2 [мужчина, брак2, компания3]', 'жена1 [женщина, брак1, компания1]']
Конечно, если у всех людей нет тегов (например, пустой кортеж), то есть только одна группа на выбор.
Не всегда существует оптимальное решение (представьте входную последовательность из 10 женщин и 2 мужчин, единственным указанным тегом является их жанр), но это делает хорошую работу настолько, насколько это возможно.
Py2 / 3-совместимый.
import random, collections
class Statistics(object):
def __init__(self):
self.tags = collections.defaultdict(int)
def account(self, tags):
for tag in tags:
self.tags[tag] += 1
def tags_value(self, tags):
return sum(1./self.tags[tag] for tag in tags)
def most_disjoined(self, tags, groups):
return max(
groups.items(),
key=lambda kv: (
-self.tags_value(kv[0] & tags),
len(kv[1]),
self.tags_value(tags - kv[0]) - self.tags_value(kv[0] - tags),
)
)
def secret_santa(people_and_their_tags):
"""Secret santa algorithm.
The lottery function expects a sequence of:
(name, tags)
For example:
[
("person1", ("male", "company1")),
("person2", ("female", "company2")),
("person3", ("male", "company1")),
("husband1", ("male", "company2", "marriage1")),
("wife1", ("female", "company1", "marriage1")),
("husband2", ("male", "company3", "marriage2")),
("wife2", ("female", "company2", "marriage2")),
]
husband1 is married to wife1 as seen by the common marriage1 tag
person1, person3 and wife1 work at the same company.
…
The algorithm will try to match people with the least common characteristics
between them, to maximize entrop— ehm, mingling!
Have fun."""
# let's split the persons into groups
groups = collections.defaultdict(list)
stats = Statistics()
for person, tags in people_and_their_tags:
tags = frozenset(tag.lower() for tag in tags)
stats.account(tags)
person= "%s [%s]" % (person, ",".join(tags))
groups[tags].append(person)
# shuffle all lists
for group in groups.values():
random.shuffle(group)
output_chain = []
prev_tags = frozenset()
while 1:
next_tags, next_group = stats.most_disjoined(prev_tags, groups)
output_chain.append(next_group.pop())
if not next_group: # it just got empty
del groups[next_tags]
if not groups: break
prev_tags = next_tags
return output_chain
if __name__ == "__main__":
example_sequence = [
("person1", ("male", "company1")),
("person2", ("female", "company2")),
("person3", ("male", "company1")),
("husband1", ("male", "company2", "marriage1")),
("wife1", ("female", "company1", "marriage1")),
("husband2", ("male", "company3", "marriage2")),
("wife2", ("female", "company2", "marriage2")),
]
print("suggested chain (each person gives present to next person)")
import pprint
pprint.pprint(secret_santa(example_sequence))
