O Natal está se aproximando rapidamente e organizando a família anual Secret Santa. Eu gostaria de tentar obter uma vantagem sobre isso, mas garantir que os casais não comprem um para o outro continua causando problemas e, apesar de fazer isso há anos, ainda há o problema que Bobé um lixo na compra de presentes para a maioria dos presenteados , Erinprovavelmente ficará desapontado, mas ele sabe que Frankgosta de Talisker, então ele é um bom parceiro para ele. Isso torna nenhuma das soluções simples existentes aceitável para minhas necessidades.

Para facilitar minha vida, sua tarefa é escrever uma função (ou alternativa mais próxima em seu idioma) que, quando recebida uma matriz de matrizes (ou alternativa mais próxima em seu idioma escolhido), devolve (ou produz) um par de 'doadores' para 'giftees' no código mais curto possível em bytes, para que as seguintes condições sejam atendidas:

• Cada nome é emparelhado com outro nome selecionado aleatoriamente a partir dos dados de entrada (Observe que nem sempre é possível aleatorizar a saída com base nas condições fornecidas)
• Os nomes serão fornecidos com uma lista de sinalizadores que representam uma matriz de adjacência com a ordem consistente, para que a coluna nse refira à mesma pessoa que a linha n.
• Se as condições não puderem ser atendidas, retorne algo falso no seu idioma.
• Se houver várias soluções, seu programa deverá ser capaz de gerá-las todas se executar várias vezes.

Você pode supor que você nunca vai ser apresentado com nomes duplicados como nós precisa ser capaz de dizer qual membro da família é que, mas você pode ser apresentado com dados que inclui espaços para diferenciar Bob Seniora partir Bob Junior! Ele deve concluir todos os casos de teste fornecidos dentro de uma hora para famílias muito grandes, como 100 nomes exclusivos nos dados de origem (consulte os exemplos de conjuntos de dados abaixo, você deve poder analisar todos eles dentro do tempo alocado).

Exemplo de entrada:

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

Dependendo do idioma, a entrada pode estar em outros formatos, por exemplo, detalhes STDIN podem ser fornecidos 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'

A saída também pode ser fornecida em qualquer formato adequado, o que for mais fácil para o seu idioma. Os formatos aceitáveis ​​incluem uma matriz de matrizes (como acima) ou talvez uma Objectmatriz de hash / / associativa ou até mesmo imprimir os aparamentos para STDOUT:

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

Em caso de dúvida, pergunte e forneça exemplos do formato de entrada necessário e do formato de saída esperado com sua resposta.

Implementação de JavaScript de referência .

Conjuntos de dados maiores: 100 , 100 , 200 , 200 - muitas soluções , 200 - apenas uma solução .

A implementação de referência conclui tudo isso em <4s na minha máquina.

Conjuntos acima gerados com este script .

Javascript ES6, 191

Esta solução retorna todos os pares possíveis como uma lista de 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]])))

Exemplo de execução:

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