Algorithme secret du père Noël

Question

Chaque Noël, nous dessinons des noms pour les échanges de cadeaux dans ma famille. Cela implique généralement des rediffusions multiples jusqu'à ce que personne n'ait retiré son conjoint. Donc, cette année, j’ai codé ma propre application de dessin de nom, qui englobe un tas de noms, un tas d’appariements non autorisés, et envoie un courrier électronique à tout le monde avec le cadeau choisi.

À l'heure actuelle, l'algorithme fonctionne comme suit (en pseudocode):

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

Quelqu'un qui en sait plus sur la théorie des graphes connaît-il une sorte d'algorithme qui fonctionnerait mieux ici? Cela fonctionne, mais je suis curieux.

EDIT: Depuis que les courriels ont été envoyés il y a quelque temps, et j'espère juste apprendre quelque chose que je reformulerai comme une question de théorie des graphes. Je ne suis pas aussi intéressé par les cas particuliers où les exclusions sont toutes les paires (comme dans les cas où les conjoints ne se font pas avoir). Je suis plus intéressé par les cas où il y a suffisamment d'exclusions pour que trouver une solution devienne la partie la plus difficile. Mon algorithme ci-dessus est juste un algorithme glouton simple que je ne suis pas sûr de réussir dans tous les cas.

Commençant par un graphe dirigé complet et une liste de paires de sommets. Pour chaque paire de sommets, supprimez l’arête du premier au deuxième sommet.

Le but est d'obtenir un graphique où chaque sommet a un bord entrant et un bord partant.

Answer 1

Créez simplement un graphique avec des arêtes reliant deux personnes si elles sont autorisées à partager des cadeaux, puis utilisez un algorithme de correspondance parfaite. (Recherchez "Chemins, arbres et fleurs" pour l’algorithme (intelligent))

Answer 2

Je n’utiliserais pas les associations non autorisées, car cela alourdit considérablement la complexité du problème. Entrez simplement le nom et l'adresse de chacun dans une liste. Créez une copie de la liste et continuez à la mélanger jusqu'à ce que les adresses figurant à chaque position des deux listes ne correspondent pas. Cela garantira que personne ne se retrouve ni ne va à leur conjoint.

En prime, si vous souhaitez utiliser ce style de scrutin secret, imprimez les enveloppes de la première liste et les noms de la deuxième liste. Ne jetez pas un coup d'oeil en bourrant les enveloppes. (Vous pouvez également automatiser l'envoi de tous les choix par courrier électronique.)

Il existe encore plus de solutions à ce problème sur ce fil .

Answer 3

Je le faisais moi-même, à la fin, l'algorithme que j'ai utilisé ne modélise pas exactement les noms de dessin à partir d'un chapeau, mais il est très proche. Fondamentalement, mélangez la liste, puis associez chaque personne à la personne suivante de la liste. La seule différence avec les noms tirés d'un chapeau est que vous obtenez un cycle au lieu de potentiellement obtenir des mini-sous-groupes de personnes qui n'échangent que des cadeaux les uns avec les autres. Si quelque chose pourrait être une fonctionnalité.

Implémentation en 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. J'ai suivi un cours de théorie des graphes, mais il est plus simple de permuter au hasard votre liste, de coupler chaque groupe consécutif, puis d'échanger tout élément non autorisé par un autre. Puisqu'il n'y a aucune personne refusée dans une paire donnée, le swap réussira toujours si vous n'autorisez pas les swaps avec le groupe sélectionné. Votre algorithme est trop complexe.

Answer 5

Créez un graphique où chaque arête est "Donabilité". Les sommets représentant les conjoints ne seront PAS adjacents. Sélectionnez un bord au hasard (c’est une cession de cadeau). Supprimez toutes les arêtes provenant du gifter et toutes les arêtes allant au récepteur, puis répétez.

Answer 6

Il existe dans la théorie des graphes un concept appelé Circuit Hamiltonien qui décrit l'objectif " objectif " vous décrivez. Un conseil pour quiconque trouve cela est de dire aux utilisateurs quelle "graine" a été utilisé pour générer le graphique. De cette façon, si vous devez recréer le graphique, vous le pouvez. La "graine" est également utile si vous devez ajouter ou supprimer une personne. Dans ce cas, il vous suffit de choisir un nouveau " graine " et générez un nouveau graphique en veillant à indiquer aux participants quelle "graine" est le dernier / actuel.

Answer 7

Je viens de créer une application Web qui fera exactement cela: http://www.secretsantaswap.com/

Mon algorithme autorise les sous-groupes. Ce n'est pas joli, mais ça marche.

fonctionne comme suit:
1. attribuer un identifiant unique à tous les participants, rappelez-vous le sous-groupe dans lequel ils se trouvent
2. dupliquer et mélanger cette liste (les cibles)
3. créer un tableau du nombre de participants dans chaque sous-groupe
4. tableau en double de [3] pour les cibles
5. créer un nouveau tableau pour les matchs finaux
6. parcourez les participants en leur assignant la première cible qui ne correspond à aucun des critères suivants:
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; A. participant == cible
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; B. participant.sousgroupe == cible.sousgroupe
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; C. le choix de la cible entraînera l'échec futur d'un sous-groupe (par exemple, le sous-groupe 1 doit toujours avoir au moins autant de cibles que les participants du sous-groupe 1, tout comme les participants restants)
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; D. participant (n + 1) == cible (n +1)
Si nous assignons la cible, nous décrémentons également les tableaux de 3 et 4

Donc, pas joli (du tout) mais ça marche. J'espère que ça aide,

Dan Carlson

Answer 8

Voici une implémentation simple en Java pour le problème du père Noël secret.

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

La solution Python ici.

Étant donné une séquence de (personne, balises) , où les balises est en soi une séquence de chaînes (éventuellement vide), mon algorithme suggère une chaîne de personnes où chaque personne donne un cadeau à la suivante dans la chaîne (la dernière personne est évidemment jumelée à la première).

Les balises existent afin de pouvoir regrouper les personnes et à chaque fois que la personne suivante est choisie dans le groupe le plus dissocié de la dernière personne choisie. La personne initiale est choisie par un ensemble vide de balises, elle sera donc sélectionnée dans le groupe le plus long.

Donc, étant donné une séquence d'entrée de:

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

une suggestion est la suivante:

['personne1 [homme, entreprise1]',  'personne2 [femme, entreprise2]',  'person3 [male, company1]',  'épouse2 [femme, mariage2, entreprise2]',  "mari1 [homme, mariage1, société2]",  "mari2 [homme, mariage2, société3]",  'épouse1 [femme, mariage1, entreprise1]']

Bien sûr, si toutes les personnes n’ont pas de balises (par exemple un tuple vide), il n’ya qu’un groupe parmi lequel choisir.

Il n’ya pas toujours de solution optimale (imaginez une séquence d’entrée de 10 femmes et 2 hommes, leur genre étant la seule balise donnée), mais cela fait du bon travail autant que possible.

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