Secret santa-Algorithmus

Nur einen Graphen mit Kanten zwischen zwei Menschen, wenn Sie berechtigt sind, Gaben zu teilen, und verwenden Sie dann ein perfektes matching Algorithmus. (Siehe "Pfade, Bäume und Blumen" für die (kluge) - Algorithmus)

War ich gerade auch Tue, am Ende des Algorithmus verwendete ich nicht genau, Modell-Zeichnung Namen aus einem Hut, aber es ist verdammt nah dran. Im Grunde schieben Sie die Liste, und dann Paaren Sie jede person mit der nächsten person in der Liste. Der einzige Unterschied mit der Zeichnung Namen aus einem Hut ist, dass Sie einen Zyklus statt der potenziell erste mini-Untergruppen von Menschen, die nur Geschenke austauschen mit einander. Wenn alles, was könnte ein feature sein.

Implementierung in 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))

Erstellen Sie einen graph, wo jeder Kante ist "giftability" Eckpunkte darstellen Ehegatten NICHT benachbart sein. Wählen Sie eine Kante im random (ist ein Geschenk-Belegung). Löschen Sie alle Kanten kommen vom gifter, und alle Kanten, gehen an den Empfänger und wiederholen.

Ich gerade eine web-app, die genau dies tun - http://www.secretsantaswap.com/

Mein Algorithmus ermöglicht Untergruppen. Es ist nicht schön, aber es funktioniert.

Arbeitet wie folgt:

1. zuweisen einer eindeutigen Kennung an alle Teilnehmer erinnern, welche Untergruppe Sie sind in

2. duplizieren und Zufall, dass die Liste (die Ziele)

3. erstellen Sie ein array mit der Anzahl der Teilnehmer in jeder Untergruppe

4. doppelte array aus [3] Ziele

5. erstellen Sie ein neues array für die final-matches

6. Durchlaufen die Teilnehmer die Zuordnung der erste Gegner, der nicht mit einem der folgenden Kriterien:

     A. Teilnehmer == Ziel

     B. Teilnehmer.Untergruppe == Ziel.Untergruppe

     C. die Wahl der Zielgruppe wird zu einer Untergruppe scheitern in der Zukunft (z.B. Untergruppe 1 muss immer mindestens so viele nicht-Untergruppe 1 Ziele übrig als Teilnehmer Untergruppe 1 Teilnehmer übrig ist)

     D. Teilnehmer(n+1) == Ziel (n +1)

Weisen wir Gegner wir auch Dekrementieren-arrays aus 3 und 4

So, nicht schön (an alle), aber es funktioniert. Hoffe es hilft,

Dan Carlson

Python-Lösung hier.

Gegeben eine Sequenz von (person, tags), wo tags ist selbst eine (möglicherweise leere) Sequenz von Zeichenfolgen, mein Algorithmus schlägt vor, eine Kette von Personen, wobei jede person gibt ein Geschenk an den nächsten in der Kette (die Letzte person, die offensichtlich gekoppelt ist mit dem ersten).

Den tags vorhanden sind, so dass die Personen gruppiert werden können, und jedes mal, wenn die nächste person ist gewählt aus der Gruppe, die am meisten dis-zusammengeschlossen, um die person, die zuletzt gewählt. Die erste person gewählt ist, durch einen leeren Satz von tags, so wird es ausgewählt werden aus der ältesten Gruppe.

Also, gegeben eine Eingabe-Sequenz:

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")),
]

einen Vorschlag:

['person1 [Männlich,weltweit1]',
'person2 [weiblich,company2]',
'person3 [Männlich,weltweit1]',
'wife2 [weiblich,marriage2,company2]',
'husband1 [Männlich,marriage1,company2]',
'husband2 [Männlich,marriage2,company3]',
'wife1 [weiblich,marriage1,weltweit1]']

Natürlich, wenn alle Personen, die keine tags (z.B. ein leeres Tupel), dann gibt es nur eine Gruppe, zum von zu wählen.

Gibt es nicht immer eine optimale Lösung (denken Sie an eine Eingabe-Sequenz von 10 Frauen und 2 Männer, Ihre genre-dem einzigen tag gegeben), aber er hat eine gute Arbeit, so viel, wie Sie können.

Py2/3 kompatibel.

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))