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

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

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

На эта ветка решений этой проблемы еще больше.

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

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

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

Реализация на 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))

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

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

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

Итак, не очень красиво, но работает. Надеюсь, это поможет,

Дэн Карлсон

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

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

Вот простая реализация на 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 здесь.

Учитывая последовательность (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))