algorithm - mrc - Algoritmo secreto de santa

house of cards big data

Question

Cada Navidad dibujamos nombres para intercambios de regalos en mi familia. Esto generalmente involucra varios redibujados hasta que nadie haya retirado a su cónyuge. Así que este año codifiqué mi propia aplicación de dibujo que incluye un montón de nombres, un grupo de emparejamientos no permitidos, 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 acerca de la teoría de grafos conoce algún tipo de algoritmo que funcione mejor aquí? Para mis propósitos, esto funciona, pero tengo curiosidad.

EDITAR: Desde que los correos electrónicos salieron hace un tiempo, y espero aprender algo, lo expresaré como una pregunta de teoría de grafos. No estoy tan interesado en los casos especiales en los que las exclusiones son todas parejas (como que los cónyuges no se conocen). Estoy más interesado en los casos en 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, elimine el borde del primer vértice al segundo.

El objetivo es obtener un gráfico en el que cada vértice tenga un borde hacia adentro y un borde hacia afuera.

Answer 1

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. asignar un identificador único a todos los participantes, recordar en qué subgrupo se encuentran
2. duplicar y mezclar esa lista (los objetivos)
3. crea una matriz de la cantidad de participantes en cada subgrupo
4. duplicar matriz de [3] para los objetivos
5. crea una nueva matriz para celebrar los partidos finales
6. itere a través de los participantes que asignan el primer objetivo que no coincide con ninguno de los siguientes criterios:
A. participante == objetivo
B. participante.Subgroup == target.Subgroup
C. elegir el objetivo provocará que un subgrupo falle en el futuro (por ejemplo, el subgrupo 1 siempre debe tener al menos tantos objetivos que no pertenecen al subgrupo 1 como participantes restantes del subgrupo 1)
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 eso ayude,

Dan Carlson

Answer 2

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 3

Cree un gráfico en el que cada borde sea "graficable". Los vértices que representan cónyuges NO serán adyacentes. Seleccione un borde al azar (que es una tarea de regalo). Elimina todos los bordes que vienen del gifter y todos los bordes van al receptor y repite.

Answer 4

Existe un concepto en la teoría de grafos llamado Circuito Hamiltoniano que describe el "objetivo" que describes. Un consejo para cualquiera que lo encuentre es decirle 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 a una persona. En ese caso, simplemente elija una nueva "semilla" y genere un nuevo gráfico, asegurándose de decirle a los participantes qué "semilla" es la actual / la última.

Answer 5

Hmmm. Tomé un curso de teoría de grafos, pero lo más simple es permutar aleatoriamente tu lista, emparejar cada grupo consecutivo y luego intercambiar cualquier elemento no permitido por otro. Dado que no hay una persona no permitida en un par dado, el intercambio siempre tendrá éxito si no permite intercambios con el grupo seleccionado. Tu algoritmo es muy complejo.

Answer 6

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 barajando hasta que las direcciones en cada posición de las dos listas no coincidan. Esto asegurará que nadie se contraiga 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 asome mientras llena los sobres. (O simplemente podría automatizar el envío de correos electrónicos a todos los que seleccionen).

Hay aún más soluciones para este problema en este hilo .

Answer 7

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

Answer 8

Simplemente lo hice yo mismo, al final el algoritmo que utilicé no modela exactamente los nombres de los dibujos, pero está bastante cerca. Básicamente baraja la lista, y luego empareja a cada persona con la siguiente persona en la lista. La única diferencia con los nombres de dibujo de un sombrero es que obtienes un ciclo en lugar de potencialmente obtener mini subgrupos de personas que solo intercambian regalos entre ellos. Si algo 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 9

Solución de Python aquí.

Dada una secuencia de (person, tags) , donde las etiquetas son en sí mismas una secuencia de cadenas (posiblemente vacía), 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 el primero).

Las etiquetas existen para que las personas se puedan agrupar y cada vez que se elija a la siguiente persona del grupo que más se haya desconectado de la última persona elegida. La persona inicial se elige mediante un conjunto de etiquetas vacías, por lo que se seleccionará 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:

[''person1 [male, company1]'', ''person2 [female, company2]'', ''person3 [male, company1]'', ''wife2 [female, marriage2, company2]'', ''husband1 [male, marriage1, company2]'', ''husband2 [male, marriage2, company3]'', ''wife1 [female, marriage1, company1]'']

Por supuesto, si todas las personas no tienen etiquetas (por ejemplo, una tupla vacía), 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), pero hace un buen trabajo tanto como puede.

Py2 / 3 compatible.

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