Algoritmo secreto de santa

Question

Cada Navidad dibujamos nombres para intercambios de regalos en mi familia. Esto generalmente implica múltiples redibujos hasta que nadie haya retirado a su cónyuge. Así que este año codifiqué mi propia aplicación de dibujo de nombres que incluye un montón de nombres, un montón de parejas no permitidas y envía un correo electrónico a todos con su regalo elegido.

En este momento, el algoritmo funciona así (en pseudocódigo):

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

¿Alguien que sepa más sobre teoría de grafos conoce algún tipo de algoritmo que funcione mejor aquí? Para mis propósitos, esto funciona, pero tengo curiosidad.

EDITAR: dado que los correos electrónicos se enviaron hace un tiempo, y solo espero aprender algo, lo reformularé como una pregunta de teoría de gráficos. No estoy tan interesado en los casos especiales en los que las exclusiones son todas parejas (como en los cónyuges que no se tienen entre sí). Estoy más interesado en los casos en los que hay suficientes exclusiones que encontrar una solución se convierte en la parte difícil. Mi algoritmo anterior es solo un algoritmo codicioso simple que no estoy seguro de que tenga éxito en todos los casos.

Comenzando con un gráfico dirigido completo y una lista de pares de vértices. Para cada par de vértices, quite el borde del primer vértice al segundo.

El objetivo es obtener un gráfico donde cada vértice tenga un borde entrando y un borde saliendo.

Answer 1

Simplemente haga un gráfico con bordes que conecte a dos personas si se les permite compartir regalos y luego use un algoritmo de correspondencia perfecto. (Busque " Caminos, árboles y flores " para el algoritmo (inteligente))

Answer 2

No usaría emparejamientos no permitidos, ya que eso aumenta enormemente la complejidad del problema. Simplemente ingrese el nombre y la dirección de todos en una lista. Cree una copia de la lista y siga barajándola hasta que las direcciones en cada posición de las dos listas no coincidan. Esto asegurará que nadie se consiga a sí mismo ni a su cónyuge.

Como beneficio adicional, si desea hacer este estilo de votación secreta, imprima sobres de la primera lista y nombres de la segunda lista. No mires mientras rellenas los sobres. (O simplemente puede automatizar el envío de correos electrónicos a todos los que elijan).

Hay incluso más soluciones a este problema en este hilo .

Answer 3

Estaba haciendo esto yo mismo, al final el algoritmo que utilicé no modela exactamente los nombres de dibujo de un sombrero, pero está muy cerca. Básicamente baraja la lista y luego empareja a cada persona con la siguiente persona de la lista. La única diferencia con sacar nombres de un sombrero es que obtienes un ciclo en lugar de potencialmente obtener mini subgrupos de personas que solo intercambian regalos entre sí. Si hay algo que podría ser una característica.

Implementación 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. Tomé un curso de teoría de grafos, pero lo más simple es permutar aleatoriamente su lista, emparejar cada grupo consecutivo y luego intercambiar cualquier elemento que no esté permitido con otro. Como no hay ninguna persona no permitida en ningún par, el intercambio siempre tendrá éxito si no permite intercambios con el grupo seleccionado. Su algoritmo es demasiado complejo.

Answer 5

Cree un gráfico donde cada arista sea "giftability" Los vértices que representan cónyuges NO serán adyacentes. Seleccione un borde al azar (que es una asignación de regalo). Elimine todos los bordes que provienen del gifter y todos los bordes que van al receptor y repita.

Answer 6

Existe un concepto en teoría de grafos llamado Hamiltonian Circuit que describe el " objetivo " tú describes. Un consejo para cualquiera que encuentre esto es decirles a los usuarios qué '' semilla '' se utilizó para generar el gráfico. De esta manera, si tiene que volver a generar el gráfico, puede hacerlo. La "semilla" También es útil si tiene que agregar o eliminar una persona. En ese caso, simplemente elija una nueva '' semilla '' y generar un nuevo gráfico, asegurándose de decir a los participantes qué '' semilla '' es el actual / último.

Answer 7

Acabo de crear una aplicación web que hará exactamente esto: http://www.secretsantaswap.com/

Mi algoritmo permite subgrupos. No es bonito, pero funciona.

Funciona de la siguiente manera:
1. asigne un identificador único a todos los participantes, recuerde en qué subgrupo están
2. duplicar y barajar esa lista (los objetivos)
3. crear una matriz de la cantidad de participantes en cada subgrupo
4. matriz duplicada de [3] para objetivos
5. crear una nueva matriz para mantener las coincidencias finales
6. iterar a través de los participantes asignando el primer objetivo que no coincide con ninguno de los siguientes criterios:
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; A. participante == objetivo
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; B. participante.Subgroup == target.Subgroup
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; C. elegir el objetivo hará que un subgrupo falle en el futuro (por ejemplo, el subgrupo 1 siempre debe tener al menos tantos objetivos no pertenecientes al subgrupo 1 como participantes restantes del subgrupo 1)
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; D. participante (n + 1) == objetivo (n +1)
Si asignamos el objetivo también disminuimos las matrices de 3 y 4

Entonces, no es bonito (en absoluto) pero funciona. Espero que ayude,

Dan Carlson

Answer 8

Aquí una implementación simple en java para el problema secreto de 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

Solución Python aquí.

Dada una secuencia de (persona, etiquetas) , donde las etiquetas son en sí mismas una secuencia (posiblemente vacía) de cadenas, mi algoritmo sugiere una cadena de personas donde cada persona da un regalo al siguiente en la cadena (la última persona obviamente está emparejada con la primera).

Las etiquetas existen para que las personas se puedan agrupar y cada vez que se elija a la siguiente persona del grupo más desunido a la última persona elegida. La persona inicial es elegida por un conjunto vacío de etiquetas, por lo que se elegirá del grupo más largo.

Entonces, dada una secuencia de entrada 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")),
]

una sugerencia es:

['persona1 [hombre, compañía1]',  'persona2 [mujer, empresa2]',  'persona3 [hombre, compañía1]',  'esposa2 [mujer, matrimonio2, compañía2]',  'marido1 [hombre, matrimonio1, compañía2]',  'marido2 [hombre, matrimonio2, compañía3]',  'esposa1 [mujer, matrimonio1, compañía1]']

Por supuesto, si todas las personas no tienen etiquetas (por ejemplo, una tupla vacía), entonces solo hay un grupo para elegir.

No siempre hay una solución óptima (piense en una secuencia de entrada de 10 mujeres y 2 hombres, siendo su género la única etiqueta dada), pero hace un buen trabajo tanto como puede.

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