Święta zbliżają się wielkimi krokami, a wraz z nimi organizowanie dorocznej rodziny Secret Santa. Chciałbym zacząć od tego, ale upewnienie się, że pary nie kupują sobie nawzajem, powoduje problemy i pomimo robienia tego przez lata nadal istnieje problem, który Bobjest dość marnotrawstwem przy zakupie prezentów dla większości darów , Erinprawdopodobnie będzie rozczarowany, ale wie, że Franklubi Talisker, więc jest dla niego dobry. To sprawia, że ​​żadne z istniejących prostych rozwiązań nie jest możliwe do zaakceptowania dla moich potrzeb.

Aby moje życie było łatwiejsze, Twoim zadaniem jest napisanie funkcji (lub najbliższej alternatywy w twoim języku), która, gdy otrzyma tablicę tablic (lub najbliższą alternatywę w wybranym przez ciebie języku), zwróci (lub wyjdzie) parę „podarunków” do „giftees” w możliwie najkrótszym kodzie w bajtach, tak aby spełnione były następujące warunki:

• Każda nazwa jest sparowana z inną, losowo wybraną nazwą z danych wejściowych (należy pamiętać, że losowanie wyniku na podstawie podanych warunków może nie zawsze być możliwe)
• Nazwy zostaną dostarczone z listą flag reprezentujących macierz przylegania z uporządkowaniem zgodnym, tak aby kolumna nodnosiła się do tej samej osoby co wiersz n.
• Jeśli warunki nie mogą być spełnione, zwróć w swoim języku coś fałszywego.
• Jeśli istnieje wiele rozwiązań, Twój program musi być w stanie wygenerować je wszystkie, jeśli zostanie uruchomiony wiele razy.

Można założyć, że nigdy nie zostaną przedstawione z takich samych nazwach jak musimy być w stanie powiedzieć, który jest członkiem rodziny, które jednak mogą być prezentowane z danymi, które zawiera spacje w celu odróżnienia Bob Seniorod Bob Junior! Powinien ukończyć wszystkie dostarczone przypadki testowe w ciągu godziny dla dość dużych rodzin, takich jak 100 unikalnych nazw w danych źródłowych (zobacz przykładowe zestawy danych poniżej, musisz być w stanie przeanalizować je wszystkie w wyznaczonym czasie).

Przykładowe dane wejściowe:

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

W zależności od języka, wejście może być w innych formatach, na przykład na szczegóły STDIN mogłyby być dostarczane jako:

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'

Dane wyjściowe mogą być również dostarczane w dowolnym rozsądnym formacie, w zależności od tego, który język jest najłatwiejszy. Dopuszczalne formaty obejmują tablicę tablic (jak wyżej) lub Objecttablicę mieszającą / / asocjacyjną, a nawet po prostu drukowanie parowań w celu STDOUT:

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

W razie wątpliwości prosimy o podanie i podanie przykładów wymaganego formatu wejściowego i oczekiwanego formatu wyjściowego wraz z odpowiedzią.

Odwołaj się do implementacji JavaScript .

Większe zestawy danych: 100 , 100 , 200 , 200 - wiele rozwiązań , 200 - tylko jedno rozwiązanie .

Implementacja referencji kończy wszystkie te czynności w <4s na moim komputerze.

Powyższe zestawy wygenerowane za pomocą tego skryptu .

JavaScript ES6, 191

To rozwiązanie zwraca wszystkie możliwe pary w postaci listy par:

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

Przykładowy przebieg:

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