La Navidad se acerca rápidamente y, junto con ella, organiza la familia anual Secret Santa. Me gustaría intentar comenzar con esto, pero asegurarme de que las parejas no compren entre sí sigue causando problemas y, a pesar de hacerlo durante años, todavía existe el problema que Bobes bastante malo al comprar regalos para la mayoría de los regalos. , Erinprobablemente estará decepcionado, pero él sabe que Frankle gusta Talisker, por lo que es un buen partido para él. Esto hace que ninguna de las soluciones simples existentes sea aceptable para mis necesidades.

Para hacerme la vida más fácil, su tarea es escribir una función (o la alternativa más cercana en su idioma) que, cuando se le da una matriz de matrices (o la alternativa más cercana en el idioma elegido), devuelve (o genera) un emparejamiento de 'gifters' para 'giftees' en el código más corto posible en bytes, de modo que se cumplan las siguientes condiciones:

• Cada nombre se combina con otro nombre, seleccionado aleatoriamente, de los datos de entrada (tenga en cuenta que no siempre es posible aleatorizar la salida en función de las condiciones proporcionadas)
• Los nombres recibirán una lista de indicadores que representan una matriz de adyacencia con el orden consistente, de modo que la columna se nrefiere a la misma persona que la fila n.
• Si no se pueden cumplir las condiciones, devuelva algo falso en su idioma.
• Si hay varias soluciones, su programa debe poder generarlas todas si se ejecuta muchas veces.

Se puede suponer que nunca se le presentará con nombres duplicados ya que tenemos que ser capaces de decir qué miembro de la familia, que es, pero es posible que se presenta con datos que incluyan espacios para diferenciar Bob Seniorentre Bob Junior! Debería completar todos los casos de prueba suministrados dentro de una hora para familias bastante grandes, como 100 nombres únicos en los datos de origen (consulte los conjuntos de datos de ejemplo a continuación, debe poder analizar todos estos dentro del tiempo asignado).

Entrada de ejemplo:

santa([
    ["Alice", 0, 0, 1, 1, 1, 1, 1],
    ["Bob",   0, 0, 0, 0, 0, 1, 0],
    ["Carla", 1, 1, 0, 0, 0, 1, 1],
    ["Dan",   1, 1, 0, 0, 0, 1, 1],
    ["Erin",  1, 1, 0, 0, 0, 1, 1],
    ["Frank", 1, 1, 1, 1, 1, 0, 1],
    ["Gary",  1, 1, 1, 1, 1, 1, 0]
]);
// might return something like:
[
    ["Alice", "Erin"],
    ["Bob", "Frank"],
    ["Carla", "Alice"],
    ["Dan", "Gary"],
    ["Erin", "Bob"],
    ["Frank", "Dan"],
    ["Gary", "Carla"]
]

santa([
    ["Alice", 0, 1, 1, 1, 0, 1],
    ["Bob",   0, 0, 1, 1, 0, 1],
    ["Carla", 0, 1, 0, 1, 0, 1],
    ["Dan",   0, 1, 1, 0, 0, 0],
    ["Erin",  0, 0, 1, 0, 0, 1],
    ["Frank", 1, 1, 1, 1, 1, 0]
]);
false

santa([
    ["Alice", 0, 1, 1],
    ["Bob",   1, 0, 1],
    ["Carla", 1, 1, 0]
]);
[
    ["Alice", "Bob"],
    ["Bob", "Carla"],
    ["Carla", "Alice"]
]

Dependiendo del idioma, la entrada puede estar en otros formatos, por ejemplo, los detalles STDIN se pueden proporcionar como:

script <<< 'Alice,0,0,1,1,1,1,1
Bob,0,0,0,0,0,1,0
Carla,1,1,0,0,0,1,1
Dan,1,1,0,0,0,1,1
Erin,1,1,0,0,0,1,1
Frank,1,1,1,1,1,0,1
Gary,1,1,1,1,1,1,0'

La salida también se puede proporcionar en cualquier formato sensible, el que sea más fácil para su idioma. Los formatos aceptables incluyen una matriz de matrices (como arriba) o tal vez una Objectmatriz asociativa / / hash / o simplemente imprimir los emparejamientos para STDOUT:

Alice:Dan
Bob:Erin
Carla:Bob
Dan:Alice
Erin:Frank
Frank:Carla

En caso de duda, pregunte y proporcione ejemplos de formato de entrada requerido y formato de salida esperado con su respuesta.

Implementación de JavaScript de referencia .

Conjuntos de datos más grandes: 100 , 100 , 200 , 200 - muchas soluciones , 200 - solo una solución .

La implementación de referencia completa todo esto en <4s en mi máquina.

Conjuntos anteriores generados con este script .

Javascript ES6, 191

Esta solución devuelve todos los emparejamientos posibles como una lista de la lista de pares:

f=l=>(h=l=>l.length,n=l.map(i=>i.shift()),o=[],(r=s=>(g=h(s))<h(n)?l[g].map((e,x)=>e&&r([...s,x])):o.push([...s]))([]),o.filter(i=>h([...new Set(i)])==h(n)).map(l=>l.map((t,f)=>[n[f],n[t]])))

Ejemplo de ejecución:

>> example = f([
    ["Alice", 0, 0, 1, 1, 1, 1, 1],
    ["Bob",   0, 0, 0, 0, 0, 1, 0],
    ["Carla", 1, 1, 0, 0, 0, 1, 1],
    ["Dan",   1, 1, 0, 0, 0, 1, 1],
    ["Erin",  1, 1, 0, 0, 0, 1, 1],
    ["Frank", 1, 1, 1, 1, 1, 0, 1],
    ["Gary",  1, 1, 1, 1, 1, 1, 0]])

<< Array [ Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], 26 more… ]

>> example[0]

<< Array [ "Alice:Carla", "Bob:Frank", "Carla:Alice", "Dan:Bob", "Erin:Gary", "Frank:Dan", "Gary:Erin" ]