Algoritmo secreto de santa

Question

Todas las Navidades sacamos 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 

¿Hay alguien que sabe más sobre la teoría de grafos conocen algún tipo de algoritmo que funcionaría mejor aquí? Para mis propósitos, esto funciona, pero tengo curiosidad.

EDIT: Dado que los correos electrónicos se publicaron hace un tiempo, y estoy esperando aprender algo, lo expresaré de nuevo 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 la izquierda.

Answer 1

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

Answer 2

No utilizaría emparejamientos no permitidos, ya que eso aumenta en gran medida 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 extra, 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 podría simplemente automatizar el envío de correos electrónicos a todos sus clientes).

Existen aún más soluciones a este problema en this thread.

Answer 3

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 4

Solo lo hice yo mismo, al final el algoritmo que utilicé no modeló los nombres de los dibujos de un sombrero, pero es bastante malditamente 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 5

Acabo de crear una aplicación web que va a hacer exactamente esto - http://www.secretsantaswap.com/

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

funciona como sigue: 1. Asignar
un identificador único para todos los participantes, recuerde qué subgrupo que están en
2. duplicado y se barajan esa lista (los objetivos)
3. crear una matriz de la serie de participantes en cada subgrupo
4. array duplicado de [3] para los objetivos
5. crear una nueva matriz para contener los partidos finales
6. iterar a través de la asignación de los participantes el primer objetivo que no coincide con cualquiera de los siguientes criterios:
          A. participante == objetivo
          B. participant.Subgroup == target.Subgroup
          C. elegir el objetivo se causar un subgrupo a fallar en el futuro (p.ej subgrupo 1 siempre debe tener al menos tantas no subgrupo 1 objetivos restantes como participantes el subgrupo 1 participantes restantes)
          D. participante (n + 1) == objetivo (n +1)
Si asignamos el objetivo también disminuimos las matrices de 3 y 4

Por lo tanto, no es bonito (en absoluto) pero funciona. Creo que sirve,

Dan Carlson

Answer 6

Crear un gráfico donde cada borde es Vértices "giftability" que representan cónyuges no serán adyacente. 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 7

Hay un concepto en la teoría de gráficos llamado Hamiltonian Circuit que describe el "objetivo" que describe. 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 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

Python solution here.

Dada una secuencia de (person, tags), donde las etiquetas son una secuencia de cadenas (posiblemente vacía), mi algoritmo sugiere una cadena de personas donde cada persona da un regalo al siguiente de 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 más 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.

Así, 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 [varón, company1]', 'Person2 [femenino, Company2]', 'persona3 [male, company1] ', ' wife2 [female, marriage2, company2] ', ' husband1 [male, marriage1, company2] ', ' husband2 [male, marriage2, company3] ', ' wife1 [female, marriage1 , compañía1] ']

Por supuesto, si todas las personas no tienen etiquetas (p. 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), 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))