Secret Santa - Revisited Christmas is fast approaching and along with it, arranging the annual family Secret Santa. I'd like to try and get a head start on this, but making sure couples don't buy for each other keeps causing problems and despite doing this for years there's still the problem that Bob is pretty rubbish at buying gifts for most of the giftees, Erin will likely be disappointed, but he knows that Frank likes Talisker, so he's a good match for him. This makes none of the existing simple solutions acceptable for my needs.

To make my life easier, your task is to write a function (or closest alternative in your language) that when given an array of arrays (or closest alternative in your chosen language), returns (or outputs) a pairing of 'gifters' to 'giftees' in the shortest possible code in bytes, such that the following conditions are met:


Each name is paired with another, randomly selected, name from the input data (Note that it may not always be possible to randomise the output based on the provided conditions)
Names will be provided with a list of flags that represent an adjacency matrix with the ordering consistent, so that column n refers to the same person as row n.
If the conditions cannot be met, return something falsy in your language.
If there are multiple solutions, your program must be able to generate them all if run many times.


You can assume you will never be presented with duplicate names as we need to be able to tell which family member is which, but you may be presented with data that includes spaces to differentiate Bob Senior from Bob Junior! It should complete all the supplied test cases within an hour  for pretty large families, such as 100 unique names in the source data (please see the example data sets below, you must be able to parse all of these within the allocated time).

Example input:

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


Depending on language, input can be in other formats, for instance details on STDIN could be provided as:

script &lt;&lt;&lt; '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'


Output can also be provided in any sensible format, whichever is easiest for your language. Acceptable formats include an array of arrays (as above) or perhaps a hash/Object/associative array or even just printing the parings to STDOUT:



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


If in doubt, please ask and provide examples of required input format and expected output format with your answer.

Reference JavaScript implementation.

Larger data sets: 100, 100, 200, 200 - many solutions, 200 - only one solution.

Reference implementation completes all these in &lt;4s on my machine.

Above sets generated with this script.
Javascript ES6, 191

This solution returns all possible pairings as a list of list of pairs:

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


Example run:

&gt;&gt; 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]])

&lt;&lt; Array [ Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], Array[7], 26 more… ]

&gt;&gt; example[0]

&lt;&lt; Array [ "Alice:Carla", "Bob:Frank", "Carla:Alice", "Dan:Bob", "Erin:Gary", "Frank:Dan", "Gary:Erin" ]