Секретный алгоритм Санты

algorithm language-agnostic graph-theory

11558 просмотра

9 ответа

39636 Репутация автора

Каждое Рождество мы рисуем имена для обмена подарками в моей семье. Это обычно включает в себя несколько перерисовок, пока никто не вытащил их супруга. Так что в этом году я написал свое собственное приложение для рисования имен, которое принимает кучу имен, кучу запрещенных пар и отправляет электронное письмо всем, у кого есть выбранный ими подарок.

Прямо сейчас алгоритм работает так (в псевдокоде):

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

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

РЕДАКТИРОВАТЬ: Так как электронные письма вышли некоторое время назад, и я просто надеюсь узнать что-то, я перефразирую это как вопрос теории графов. Меня не очень интересуют особые случаи, когда исключениями являются все пары (например, супруги не получают друг друга). Меня больше интересуют случаи, когда существует достаточно исключений, когда поиск любого решения становится трудной частью. Мой алгоритм, приведенный выше, является простым жадным алгоритмом, который, я не уверен, будет успешным во всех случаях.

Начиная с полного ориентированного графа и списка пар вершин. Для каждой пары вершин удалите ребро от первой вершины до второй.

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

Автор: Eclipse Источник Размещён: 07.11.2008 08:34

Ответы (9)


6 плюса

307502 Репутация автора

Я бы не стал использовать запрещенные пары, поскольку это значительно усложняет задачу. Просто введите имя и адрес каждого в список. Создайте копию списка и продолжайте перетасовывать ее, пока адреса в каждой позиции двух списков не совпадут. Это гарантирует, что никто не получит себя или своего супруга.

В качестве бонуса, если вы хотите использовать этот секретный стиль голосования, печатайте конверты из первого списка и имена из второго списка. Не заглядывайте, когда набиваете конверты. (Или вы можете просто автоматизировать рассылку по электронной почте всем, кого выбираете.)

Есть еще больше решений этой проблемы в этой теме .

Автор: Bill the Lizard Размещён: 07.11.2008 08:37

5 плюса

19050 Репутация автора

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

Автор: Brian Размещён: 07.11.2008 08:40

9 плюса

166 Репутация автора

Решение

Просто создайте график с ребрами, соединяющими двух людей, если им разрешено делиться подарками, а затем используйте алгоритм идеального соответствия. (Ищите «Пути, деревья и цветы» для (умного) алгоритма)

Автор: Watson Ladd Размещён: 07.11.2008 10:14

6 плюса

3257 Репутация автора

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

Реализация в 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))
Автор: wxs Размещён: 19.11.2008 09:43

1 плюс

11 Репутация автора

Я только что создал веб-приложение, которое будет делать именно это - http://www.secretsantaswap.com/

Мой алгоритм учитывает подгруппы. Это не красиво, но это работает.

Работает следующим образом:
1. назначить уникальный идентификатор всем участникам, запомнить, в какой подгруппе они находятся
2. дублировать и перемешать этот список (цели)
3. создать массив из числа участников в каждой подгруппе
4. дублировать массив из [3] для целей
5. создайте новый массив для хранения финальных матчей
6. переберите участников, назначающих первую цель, которая не соответствует ни одному из следующих критериев:
     A. участник == цель
     B. участник.Subgroup == цель . Подгруппа
     C. выбор цели приведет к сбою подгруппы в будущем (например, в подгруппе 1 всегда должно быть как минимум столько же целей, не относящихся к подгруппе 1, сколько осталось участников в подгруппе 1 участников)
     D. участник (n + 1) == цель (n + 1).
Если мы назначаем цель, мы также уменьшаем массивы с 3 и 4

Так что не очень (вообще), но это работает. Надеюсь, это поможет,

Дэн Карлсон

Автор: dancarlson Размещён: 28.11.2008 03:39

2 плюса

21 Репутация автора

Создайте график, в котором каждое ребро является «подарочной» Вершины, которые представляют супругов, НЕ будут смежными. Выберите ребро наугад (это подарок). Удалите все ребра, идущие от подарка, и все ребра, идущие к приемнику, и повторите.

Автор: Eddie Rowe Размещён: 10.11.2010 08:57

2 плюса

13404 Репутация автора

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

Автор: dana Размещён: 31.12.2011 06:33

1 плюс

319 Репутация автора

Вот простая реализация в 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));
    }
}
Автор: suizo Размещён: 11.10.2012 12:50

0 плюса

69174 Репутация автора

Python решение здесь.

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

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

Итак, с учетом входной последовательности:

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))
Автор: tzot Размещён: 24.11.2017 06:00
Вопросы из категории :
32x32