Wichteln Algorithmus

Question

Jedes Jahr zu Weihnachten ziehen wir Namen für Geschenkaustäusche in meiner Familie. In der Regel erfolgt mulitple neu gezeichnet, bis niemand ihre Ehepartner gezogen hat. Also in diesem Jahr codiert ich meinen eigenen Namen Zeichnung app, die in einer Reihe von Namen nimmt, ein Bündel von nicht anerkannten Paarungen und eine E-Mail an alle mit ihrem gewählten giftee sendet aus.

Im Moment arbeitet der Algorithmus wie folgt aus (in Pseudo-Code):

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

Hat jemand, der mehr über Graphentheorie kennt eine Art von Algorithmus kennt, die hier besser funktionieren würde? Für meine Zwecke funktioniert, aber ich bin neugierig.

EDIT: Da die E-Mails vor einer Weile gingen, und ich bin nur die Hoffnung, etwas zu lernen ich dies als eine Graphentheorie Frage anders formulieren würde. Ich bin nicht so interessiert in den besonderen Fällen, in denen die Ausschlüsse sind alle Paare (wie in Ehegatten sie nicht immer). Ich bin mehr daran interessiert, in den Fällen, in denen es genügend Ausnahmen sind, dass jede Lösung zu finden, der schwierige Teil wird. Mein Algorithmus oben ist nur ein einfacher Greedy-Algorithmus, die ich bin nicht sicher, in allen Fällen gelingen würde.

Beginnend mit einem vollständigen gerichteten Graphen und einer Liste der Knotenpaar. Für jedes Knotenpaar, entfernen Sie den Rand von dem ersten Eckpunkt zu dem zweiten.

Das Ziel ist es, ein Diagramm zu erhalten, wo jede Ecke eine Kante in der kommenden aufweist und ein Rand zu verlassen.

Answer 1

Nur eine grafische Darstellung mit Kanten machen den Anschluss von zwei Personen, wenn sie berechtigt sind, Geschenke zu teilen und dann einen perfekten Matching-Algorithmus verwenden. (Suchen Sie nach „Wegen, Bäumen und Blumen“ für den (klug) Algorithmus)

Answer 2

Ich würde nicht disallowed Paarungen verwenden, da dies erheblich die Komplexität des Problems erhöht. Geben Sie alle Namen und Adresse in eine Liste. Erstellen Sie eine Kopie der Liste und halten, bis die Adressen in jeder Position der beiden Listen schlurfenden stimmen nicht überein. Dadurch wird sichergestellt, dass niemand bekommt selbst oder ihre Ehepartner.

Als Bonus, wenn du dieses Geheimnis-Stimmzettel-Stil tun wollen, Drucken von Umschlägen aus der ersten Liste und Namen aus der zweiten Liste. peek nicht während der Umschläge Füllung. (Oder Sie könnten automatisieren nur jeden thier Pick E-Mail).

Es gibt noch mehr Lösungen für dieses Problem auf dieses Thema .

Answer 3

Ich war gerade dabei, diese selbst, am Ende des Algorithmus I tut verwendet nicht genau Modellzeichnung Namen aus einem Hut, aber es ist verdammt nah. Grundsätzlich mischte die Liste, und dann jede Person mit der nächsten Person in der Liste paaren. Der einzige Unterschied mit Namen aus einem Hut Zeichnung ist, dass Sie einen Zyklus erhalten anstelle von potentiell Minigruppen von Leuten, die nur tauschen Geschenke miteinander. Wenn alles, was ein Merkmal sein könnte.

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

Answer 4

Hmmm. Ich habe einen Kurs in der Graphentheorie, aber einfacher ist es, nur die Liste zufällig permutiert, paart jede aufeinanderfolgende Gruppe, dann jedes Element tauschen, die mit einem anderen nicht zulässig ist. Da es in einem bestimmten Paar keine unzulässige Person ist, gelingt es der Swap wird immer, wenn Sie Swaps mit der Gruppe nicht zulassen ausgewählt. Ihr Algorithmus ist zu komplex.

Answer 5

ein Diagramm erstellen, in dem jede Kante „giftability“ Vertices ist, die Ehepartner vertreten wird nicht benachbart sein. Wählen Sie eine Kante nach dem Zufallsprinzip (das ist ein Geschenk Zuweisung). Löschen Sie alle Kanten aus dem gifter kommen und alle Kanten an den Empfänger, und wiederholen Sie gehen.

Answer 6

Es gibt ein Konzept in der Graphentheorie ein Hamilton-Schaltung genannt, der das „Ziel“ Sie beschreibt beschreiben. Ein Tipp für jeden, der diese findet, ist den Benutzern zu sagen, die „Samen“ verwendet wurde, um die Grafik zu erzeugen. Auf diese Weise, wenn Sie neu zu erzeugen, um das Diagramm Sie können. Der „Samen“ ist auch nützlich, wenn Sie eine Person hinzufügen oder entfernen. In diesem Fall einfach ein neues „Samen“ wählen und einen neuen Graphen erzeugen, um sicherzustellen, Teilnehmer zu sagen, welche „Samen“ ist die aktuelle / neueste.

Answer 7

Ich habe gerade eine Web-Anwendung, die tut genau das - http://www.secretsantaswap.com/

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

arbeitet wie folgt:
1. zuweisen eine eindeutige Kennung an alle Teilnehmer, erinnern, welche Untergruppe sie sind in
2. duplizieren und mischt diese Liste (die Ziele)
3. eine Anordnung von der Anzahl der Teilnehmer in jeder Untergruppe erstellen
4. duplizieren Array aus [3] für Ziele
5. ein neues Array erstellen, um die Finalspiele zu halten
6. durchlaufen die Teilnehmer das erste Ziel zuweisen, die nicht eines der folgenden Kriterien übereinstimmen:
A. Teilnehmer == Ziel
B. participant.Subgroup == target.Subgroup
C. das Ziel der Auswahl bewirkt, dass eine Untergruppe in der Zukunft versagen (z Untergruppe 1 muss immer mindestens so viele Nicht-Untergruppe 1 Ziele verbleibenden Teilnehmer als Untergruppe 1 Teilnehmer verbleibend)
D. Teilnehmer (n + 1) == Ziel (n + 1)
Wenn wir das Ziel, das wir auch verringern, die Arrays von 3 und 4

zuweisen

Also, nicht schön (überhaupt), aber es funktioniert. Hoffe, dass es hilft,

Dan Carlson

Answer 8

Hier ist eine einfache Implementierung in Java für das Wichteln Problem.

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

Answer 9

Python Lösung.

eine Folge von (person, tags) gegeben, wo Tags selbst eine (möglicherweise leeren) Folge von Strings, schlägt mein Algorithmus eine Kette von Personen, wo jede Person ein Geschenk an den nächsten in der Kette gibt (die letzte Person, offensichtlich mit der gepaart ist erster).

Die Tags vorhanden sein, damit die Personen, gruppiert werden können und jedes Mal, wenn die nächste Person, die aus der Gruppe ausgewählt meisten dis verbundenen gewählt wird an die letzte Person. Die anfängliche Person durch einen leeren Satz von Tags gewählt wird, so wird es von der längsten Gruppe aufgenommen werden.

So, da eine Eingangssequenz von:

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

ein Vorschlag:

[ 'person1 [männlich, company1]',  'Person2 [female, company2]',  'Person3 [männlich, company1]',  'Wife2 [weiblich, marriage2, company2]',  'Husband1 [männlich, marriage1, company2]',  'Husband2 [männlich, marriage2, company3]',  'Wife1 [weiblich, marriage1, company1]]

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

Es ist nicht immer eine optimale Lösung (man denke an eine Eingangssequenz von 10 Frauen und 2 Männer, ihr Genre der einzige Tag gegeben wird), aber es hat eine gute Arbeit, so viel wie er kann.

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