Algoritmo segreto di Babbo Natale

Question

Ogni Natale disegniamo nomi per scambi di regali nella mia famiglia. Questo di solito comporta ridisegnazioni multiple fino a quando nessuno ha tirato fuori il coniuge. Quindi quest'anno ho codificato la mia app per il disegno del nome che contiene un sacco di nomi, un mucchio di abbinamenti non consentiti e invia un'email a tutti con la giftee prescelta.

Al momento, l'algoritmo funziona in questo modo (in pseudocodice):

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

Qualcuno che sa di più sulla teoria dei grafi conosce qualche tipo di algoritmo che funzionerebbe meglio qui? Per i miei scopi, funziona, ma sono curioso.

EDIT: dato che le e-mail sono uscite un po 'di tempo fa e spero solo di imparare qualcosa, lo riformulo come una domanda di teoria dei grafi. Non sono così interessato ai casi speciali in cui le esclusioni sono tutte coppie (come se i coniugi non si scambiassero). Sono più interessato ai casi in cui ci sono abbastanza esclusioni che trovare una soluzione diventa la parte difficile. Il mio algoritmo sopra è solo un semplice algoritmo avido che non sono sicuro avrebbe successo in tutti i casi.

Iniziando con un grafico diretto completo e un elenco di coppie di vertici. Per ogni coppia di vertici, rimuovi il bordo dal primo vertice al secondo.

L'obiettivo è ottenere un grafico in cui ogni vertice ha un bordo in arrivo e un bordo in uscita.

Answer 1

Basta creare un grafico con i bordi che collegano due persone se sono autorizzati a condividere regali e quindi utilizzare un algoritmo di corrispondenza perfetto. (Cerca " Percorsi, alberi e fiori " per l'algoritmo (intelligente))

Answer 2

Non userei accoppiamenti non consentiti, poiché ciò aumenta notevolmente la complessità del problema. Basta inserire il nome e l'indirizzo di tutti in un elenco. Crea una copia dell'elenco e continua a mescolarlo fino a quando gli indirizzi in ciascuna posizione dei due elenchi non corrispondono. Ciò garantirà che nessuno ottenga se stesso o il proprio coniuge.

Come bonus, se vuoi fare questo scrutinio segreto, stampa le buste dal primo elenco e i nomi dal secondo elenco. Non sbirciare mentre riempi le buste. (O potresti semplicemente automatizzare la posta elettronica a tutti la loro scelta.)

Esistono ancora più soluzioni a questo problema su questa discussione .

Answer 3

Lo stavo facendo da solo, alla fine l'algoritmo che ho usato non modella esattamente i nomi di un cappello, ma è abbastanza vicino. Fondamentalmente mescolare l'elenco, quindi associare ogni persona alla persona successiva nell'elenco. L'unica differenza con l'estrazione di nomi da un cappello è che ottieni un ciclo invece di potenzialmente ottenere mini sottogruppi di persone che si scambiano regali solo tra loro. Se qualcosa che potrebbe essere una caratteristica.

Implementazione 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. Ho seguito un corso di teoria dei grafi, ma è più semplice permutare casualmente la tua lista, accoppiare ogni gruppo consecutivo, quindi scambiare qualsiasi elemento non consentito con un altro. Poiché non esiste una persona non consentita in una determinata coppia, lo scambio avrà sempre successo se non si consentono gli scambi con il gruppo selezionato. Il tuo algoritmo è troppo complesso.

Answer 5

Crea un grafico in cui ciascun bordo è "quotabile" " I vertici che rappresentano i coniugi NON saranno adiacenti. Seleziona un bordo a caso (ovvero un incarico regalo). Elimina tutti i bordi provenienti dalla gifter e tutti i bordi che vanno al ricevitore e ripeti.

Answer 6

Nella teoria dei grafi esiste un concetto chiamato Circuito hamiltoniano che descrive l'obiettivo "quot" tu descrivi. Un suggerimento per chiunque lo trovi è quello di dire agli utenti quale "seed" è stato usato per generare il grafico. In questo modo, se è necessario rigenerare il grafico, è possibile. Il "seme" è utile anche se devi aggiungere o rimuovere una persona. In tal caso, scegli semplicemente un nuovo "seme" e genera un nuovo grafico, assicurandoti di dire ai partecipanti quale "seed" è l'attuale / più recente.

Answer 7

Ho appena creato un'app Web che farà esattamente questo - http://www.secretsantaswap.com/

Il mio algoritmo consente sottogruppi. Non è carino, ma funziona.

Funziona come segue:
1. assegnare un identificatore univoco a tutti i partecipanti, ricordare in quale sottogruppo si trovano Pagina 2. duplica e rimescola quell'elenco (i target) Pagina 3. creare una matrice del numero di partecipanti in ciascun sottogruppo Pagina 4. array duplicato da [3] per target
5. crea un nuovo array per contenere le partite finali Pagina 6. scorrere i partecipanti assegnando il primo target che non corrisponde a nessuno dei seguenti criteri: Hotel & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; A. partecipante == target Hotel & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; B. participant.Subgroup == target.Subgroup Hotel & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; C. la scelta dell'obiettivo provocherà il fallimento di un sottogruppo in futuro (ad es. il sottogruppo 1 deve sempre avere almeno altrettanti target non di sottogruppo 1 quanti rimanenti partecipanti del sottogruppo 1)
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; D. partecipante (n + 1) == target (n +1)
Se assegniamo il target, diminuiamo anche le matrici da 3 e 4

Quindi, non carina (per niente) ma funziona. Spero che sia d'aiuto,

Dan Carlson

Answer 8

Ecco una semplice implementazione in java per il problema segreto di santa.

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

Soluzione Python qui.

Data una sequenza di (persona, tag) , in cui i tag sono essi stessi una sequenza (possibilmente vuota) di stringhe, il mio algoritmo suggerisce una catena di persone in cui ogni persona dà un regalo al prossimo in la catena (l'ultima persona è ovviamente abbinata alla prima).

I tag esistono in modo che le persone possano essere raggruppate e ogni volta che la persona successiva viene scelta dal gruppo più dis-unito all'ultima persona scelta. La persona iniziale viene scelta da un set vuoto di tag, quindi verrà scelta dal gruppo più lungo.

Quindi, data una sequenza di input di:

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

un suggerimento è:

['person1 [male, company1]',  "person2 [female, company2]",  "person3 [male, company1]",  "moglie2 [femmina, matrimonio2, compagnia2]",  "marito1 [maschio, matrimonio1, compagnia2]",  "marito2 [maschio, matrimonio2, compagnia3]",  'moglie1 [femmina, matrimonio1, compagnia1]']

Naturalmente, se tutte le persone non hanno tag (ad esempio una tupla vuota), c'è solo un gruppo tra cui scegliere.

Non c'è sempre una soluzione ottimale (pensa a una sequenza di input di 10 donne e 2 uomini, il cui genere è l'unico tag dato), ma fa un buon lavoro il più possibile.

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