Natal semakin dekat dan bersamaan dengan itu, mengatur Santa Secret keluarga tahunan. Saya ingin mencoba dan memulainya, tetapi memastikan pasangan tidak membeli untuk satu sama lain terus menyebabkan masalah dan meskipun melakukan ini selama bertahun-tahun masih ada masalah yang Bobcukup sampah dalam membeli hadiah untuk sebagian besar penerima hadiah , Erinkemungkinan akan kecewa, tapi dia tahu itu Franksuka Talisker, jadi dia pasangan yang cocok untuknya. Ini membuat tidak ada solusi sederhana yang ada yang dapat diterima untuk kebutuhan saya.

Untuk membuat hidup saya lebih mudah, tugas Anda adalah menulis fungsi (atau alternatif terdekat dalam bahasa Anda) yang ketika diberi array array (atau alternatif terdekat dalam bahasa yang Anda pilih), mengembalikan (atau menghasilkan) pasangan 'gifters' ke 'giftees' dalam kode sesingkat mungkin dalam byte, sehingga kondisi berikut terpenuhi:

• Setiap nama dipasangkan dengan yang lain, dipilih secara acak, nama dari data input (Perhatikan bahwa tidak selalu mungkin untuk mengacak output berdasarkan kondisi yang disediakan)
• Nama akan diberikan daftar flag yang mewakili matriks adjacency dengan urutan yang konsisten, sehingga kolom nmerujuk ke orang yang sama dengan baris n.
• Jika kondisi tidak dapat dipenuhi, kembalikan sesuatu yang salah dalam bahasa Anda.
• Jika ada beberapa solusi, program Anda harus dapat menghasilkan semuanya jika dijalankan berkali-kali.

Anda dapat berasumsi bahwa Anda tidak akan pernah disajikan dengan nama duplikat karena kami harus dapat memberi tahu anggota keluarga mana yang mana, tetapi Anda mungkin diberikan data yang mencakup ruang untuk membedakan Bob Seniordari Bob Junior! Ini harus menyelesaikan semua kasus uji yang disediakan dalam satu jam untuk keluarga yang cukup besar, seperti 100 nama unik dalam data sumber (harap lihat contoh kumpulan data di bawah ini, Anda harus dapat menguraikan semua ini dalam waktu yang dialokasikan).

Input contoh:

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

Bergantung pada bahasa, input dapat dalam format lain, misalnya detail pada STDIN dapat diberikan sebagai:

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'

Output juga dapat diberikan dalam format apa pun yang masuk akal, mana yang paling mudah untuk bahasa Anda. Format yang dapat diterima termasuk array array (seperti di atas) atau mungkin Objectarray hash / / asosiatif atau bahkan hanya mencetak paring ke STDOUT:

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

Jika ragu, tanyakan dan berikan contoh format input yang diperlukan dan format output yang diharapkan dengan jawaban Anda.

Referensi implementasi JavaScript .

Kumpulan data yang lebih besar: 100 , 100 , 200 , 200 - banyak solusi , 200 - hanya satu solusi .

Implementasi referensi melengkapi semua ini dalam <4s di mesin saya.

Kumpulan di atas dibuat dengan skrip ini .

Javascript ES6, 191

Solusi ini mengembalikan semua pasangan yang memungkinkan sebagai daftar daftar pasangan:

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

Contoh dijalankan:

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