Noël approche à grands pas et avec lui, l'organisation du Père Noël secret familial annuel. J'aimerais essayer de prendre une longueur d'avance à ce sujet, mais faire en sorte que les couples n'achètent pas l'un pour l'autre continue de causer des problèmes et malgré cela pendant des années, il y a toujours le problème qui Bobest assez nul pour acheter des cadeaux pour la plupart des giftees , Erinsera probablement déçu, mais il sait qu'il Frankaime Talisker, donc c'est un bon match pour lui. Cela ne rend aucune des solutions simples existantes acceptable pour mes besoins.

Pour me faciliter la vie, votre tâche consiste à écrire une fonction (ou l'alternative la plus proche dans votre langue) qui, lorsqu'elle reçoit un tableau de tableaux (ou l'alternative la plus proche dans la langue choisie), renvoie (ou génère) une paire de `` cadeaux '' à 'giftees' dans le code le plus court possible en octets, de sorte que les conditions suivantes soient remplies:

• Chaque nom est associé à un autre nom, sélectionné au hasard, à partir des données d'entrée (notez qu'il n'est pas toujours possible de randomiser la sortie en fonction des conditions fournies)
• Les noms seront fournis avec une liste de drapeaux qui représentent une matrice d'adjacence avec l'ordre cohérent, de sorte que la colonne se nréfère à la même personne que la ligne n.
• Si les conditions ne peuvent pas être remplies, renvoyez quelque chose de faux dans votre langue.
• S'il existe plusieurs solutions, votre programme doit pouvoir toutes les générer s'il est exécuté plusieurs fois.

Vous pouvez supposer que vous ne serez jamais présenté avec des noms en double que nous devons être en mesure de dire quel membre de la famille est qui, mais vous pouvez être présenté avec des données qui comprend des espaces pour se différencier Bob Seniorde Bob Junior! Il devrait compléter tous les cas de test fournis dans l'heure pour les familles assez grandes, telles que 100 noms uniques dans les données source (veuillez consulter les exemples d'ensembles de données ci-dessous, vous devez être en mesure de les analyser tous dans le temps imparti).

Exemple d'entrée:

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

Selon la langue, l'entrée peut être dans d'autres formats, par exemple des détails sur STDIN peuvent être fournis comme suit:

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 sortie peut également être fournie dans n'importe quel format sensible, selon ce qui est le plus simple pour votre langue. Les formats acceptables incluent un tableau de tableaux (comme ci-dessus) ou peut-être un Objecttableau de hachage / / associatif ou même simplement l'impression des parures à STDOUT:

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

En cas de doute, veuillez demander et fournir des exemples de format d'entrée requis et de format de sortie attendu avec votre réponse.

Référence à l'implémentation JavaScript .

De plus grands ensembles de données: 100 , 100 , 200 , 200 - plusieurs solutions , 200 - une seule solution .

L'implémentation de référence complète tout cela en <4s sur ma machine.

Ensembles ci-dessus générés avec ce script .

Javascript ES6, 191

Cette solution renvoie tous les appariements possibles sous forme de liste de liste de paires:

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

Exemple d'exécution:

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