Prinsip Permutation-Pigeon-hole

25

Dalam permainan sudoku, banyak pemain suka "memasukkan" angka-angka yang mungkin ada di setiap kotak:

Baris Sudoku

Baris di atas dapat direpresentasikan sebagai array:

[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [1,2,4], [8]]

Sekarang, perhatikan bahwa hanya ada 1 tempat di mana 4bisa pergi. Ini secara efektif memungkinkan kita menyederhanakan daftar di atas menjadi:

[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [4], [8]]

Tujuan dari tantangan ini adalah untuk mengambil daftar nomor yang mungkin dalam permutasi, dan menyimpulkan kemungkinan yang dapat dihilangkan .

Sebagai contoh lain, katakanlah Anda memiliki berbagai kemungkinan berikut:

[[0,1,3], [0,2,3], [1,2], [1,2]]

Dua tempat terakhir harus diisi dengan 1 dan 2. Oleh karena itu, kita dapat menghapus kemungkinan itu dari dua elemen pertama dalam array:

[[0,3], [0,3], [1,2], [1,2]]

Sebagai contoh lain:

[[0,1,2,3], [0,2], [0,2], [0,2]]

Tidak mungkin untuk membangun permutasi dari kemungkinan di atas, karena hanya ada 1 lokasi untuk keduanya 1dan 3, dan Anda ingin mengembalikan array kosong.

Anda perlu memasukkan daftar kemungkinan dan menampilkan kemungkinan yang tersisa setelah jumlah maksimum kemungkinan telah dieliminasi.

  • Jika array tertentu tidak mungkin, Anda harus mengembalikan array kosong, atau array di mana salah satu sub-array kosong.
  • Anda dapat mengasumsikan bahwa array akan terbentuk dengan baik, dan memiliki setidaknya 1 elemen.
  • Diberikan array ukuran N, Anda dapat menganggap angka-angka dalam subarray akan selalu berada dalam kisaran [0:N), dan ituN <= 10
  • Anda tidak boleh berasumsi bahwa setiap nomor dari 0hingga N-1akan ada
  • Anda dapat berasumsi bahwa angka-angka dalam satu subarray unik.
  • Jika sebuah subarray hanya berisi satu kemungkinan, Anda bisa mewakili kemungkinan itu dalam sebuah array atau dengan sendirinya. [[1],[2],[0]], [1,2,0], [[1,2],0,[1,2]]Semuanya valid.
  • Anda dapat menerima array baik dalam format string yang masuk akal atau dalam format daftar / array.
  • Subarrays bisa dalam urutan apa pun.
  • Alih-alih berurusan dengan array kasar, Anda dapat mengisi tempat kosong dengan -1.

Uji kasus

[[0]]                                         -> [[0]]
[[1],[0]]                                     -> [[1],[0]]
[[1],[1]]                                     -> []
[[1],[0,1]]                                   -> [[1],[0]]
[[0,1,2],[1,2],[1,2]]                         -> [[0],[1,2],[1,2]]
[[0,1],[1,2],[0,2]]                           -> [[0,1],[1,2],[0,2]]
[[2,1],[1,2],[1,2]]                           -> []
[[0,3],[2,1],[3,0],[3,2]]                     -> [[0,3],[1],[0,3],[2]]
[[0,1],[0,1],[2,3],[2,3,0]]                   -> [[0,1],[0,1],[2,3],[2,3]]
[[0,1],[0,3],[3,2],[0]]                       -> [[1],[3],[2],[0]]
[[3,5,2],[0,2,4],[4,0],[0,1,3,5],[2,1],[2,4]] -> [[3,5],[0,2,4],[4,0],[3,5],[1],[2,4]]
[[6,9,8,4],[4,5],[5,3,6],[3,8,6,1,4],[3,1,9,6],[3,7,0,2,4,5],[9,5,6,8],[6,5,8,1,3,7],[8],[8,0,6,2,5,6,3]] -> [[6,9,4],[4,5],[5,3,6],[3,6,1,4],[3,1,9,6],[0,2],[9,5,6],[7],[8],[0,2]]
[[3,5,0],[5,7],[5,1,2],[1,3,0],[5,3],[5,0],[5,3,7,8,0,6],[7,5,0,1,8],[1,0,8],[0,6]] -> []
[[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]] -> [[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]]
[[2,6,0],[0,4,3],[0,6,2],[0,7],[0,9,2,3,6,1,4],[1,7,2],[2,7,8],[8,6,7],[6,5,2,8,0],[5,8,1,4]] -> [[2,6,0],[3],[0,6,2],[0,7],[9],[1],[2,7,8],[8,6,7],[5],[4]]
[[8],[8,0,6,5,7,2,4,1],[8,6,9,3,5,0,7],[3,9,1,0],[9],[9,2,6],[2,8,3],[3,1,6,8,2],[6],[6,4,5,3,0,7]] -> [[8],[5,7,4],[5,7],[0],[9],[2],[3],[1],[6],[4,5,7]]
[[8,1,0],[5,8,7,6,2,0],[6,8,2],[2,4,0,9],[4,1,7,3,6,8],[8,1],[8,0,3],[0,8,2],[0,8,3],[1,8,0]] -> []

Ini adalah jadi buat jawaban Anda sesingkat mungkin!

Nathan Merrill
sumber
Adakah angka yang lebih besar dari 9?
Leaky Nun
Anda tidak perlu mendukung angka yang lebih besar dari 9.
Nathan Merrill
Bisakah saya kembali dengan duplikat dalam format sub-array?
Leaky Nun
@ LeakyNun no. Subarrays hanya dapat berisi elemen unik.
Nathan Merrill
Saya pikir Anda memiliki beberapa kesalahan dalam test case keempat Anda; salah satu sublist ini diberi tanda kurung ganda.
TheBikingViking

Jawaban:

17

Brachylog , 21 byte

:1fz:da|,[]
:2a#d
:Am

Cobalah online!

Cobalah online!

Predikat 0 (predikat utama)

:1fz:da|,[]
:1f            Find all solutions of Predicate 1 using Input as Input.
   z           Transpose
    :da        Deduplicate each.
       |,[]    If there is no solution, return [] instead.

Predikat 1 (predikat bantu 1)

:2a#d
:2a     Each element of Output satisfies Predicate 2 with each element of Input as Input
   #d   Each element is different

Predikat 2 (predikat bantu 2)

:Am     Output is member of Input
Biarawati Bocor
sumber
8

Jelly , 10 byte

Œp⁼Q$ÐfZQ€

Cobalah online!

Œp⁼Q$ÐfZQ€   Main chain, argument: z

Œp           Cartesian product
  ⁼Q$Ðf      Filter for those that remain unchanged when uniquified
       Z     Transpose
        Q€   Uniquify each subarray
Biarawati Bocor
sumber
Tampaknya agak tidak jujur ​​untuk mengklaim 10 byte ketika Jelly menggunakan karakter di luar latin1. Diwakili sebagai UTF-8 urutan di atas membutuhkan 16 byte.
Chris Becke
1
@ChrisBecke Jelly memiliki charset sendiri
Robin Gertenbach
Namun - jika saya mencobanya secara online! - Saya perlu mengirim 16 byte.
Chris Becke
@ ChrisBecke Ya, tetapi jika Anda mengunduh Jelly, Anda hanya perlu menulis program 10 byte.
Leaky Nun
Dan simpan dalam file teks yang tidak bisa saya edit selain Jelly? Dengan argumen itu jika Jelly mengkompres programnya, kita hanya harus menghitung byte yang dikompres?
Chris Becke
7

Pyth , 11 byte

{MC{I#.nM*F

Cobalah online!

{MC{I#.nM*F
         *F  reduce by Cartesian product
             produces nested arrays
      .nM    flatten each
   {I#       filter for invariant under deduplication
  C          transpose
{M           deduplicate each
Biarawati Bocor
sumber
6

Haskell, 100 byte

import Data.List
p z=map nub$transpose$filter(and.(flip$zipWith elem)z)$permutations[0..length z-1]
Geoff Reedy
sumber
Solusi bagus! and.flip(zipWith elem)zlebih pendek
Damien
2

Python 3, 101 99 byte

Berkat @TLW untuk -2 byte

from itertools import*
lambda x:list(map(set,zip(*[i for i in product(*x)if len(i)==len(set(i))])))

Fungsi anonim yang mengambil input melalui argumen dari daftar daftar dan mengembalikan daftar set.

Bagaimana itu bekerja

from itertools import*        Import Python's library for iterator generation
lambda x                      Anonymous function with input possibilities x as a
                              list of lists
...for i in product(*x)...    For i in the Cartesian product of x, ie all candidate
                              arrangements:
[...if len(i)==len(set(i))]    Filter into list by non-duplicity (set removes
                               duplicates, so there are no duplicates if the length
                               of i is the same as the length of the set of
                               the elements of i)
zip(*...)                     Unpack and take the transpose, leaving the modified
                              possibilities with duplicates
map(set,...)                  Remove duplicates
:list(...)                    Return the modified possibilities as a list of sets

Cobalah di Ideone

TheBikingViking
sumber
list(map(set,lebih pendek, saya pikir
TLW
2

Mathematica, 46 byte

Union/@Thread@Select[Tuples@#,DuplicateFreeQ]&
alephalpha
sumber
0

PHP, 245 231 byte

131 117 untuk fungsi produk kartesius, 114 untuk hal-hal lain

function c($a){if ($a){if($u=array_pop($a))foreach(c($a)as$p)foreach($u as$v)yield $p+[count($p)=>$v];}else yield[];}
function p($a){foreach(c($a)as$i)if(max(array_count_values($i))<2)foreach($i as$k=>$v)$r[$k][$v]=$v;return$r?:[];}

Saya mengalami masalah memori pada beberapa kasus uji, dengan fungsi rekursif untuk produk kartesius. Bekerja lebih baik dengan kelas generator ini dan function c($a){$b=[];foreach($a as$i)$b[]=new \ArrayIterator($i);return new CartesianProductIterator($b);}.
Tetapi generator saya lebih pendek dan melakukan pekerjaan yang sama.

Contoh-contoh yang lebih besar, bagaimanapun, menghasilkan Kesalahan Server Internal (baik dengan iterator dan generator) setelah beberapa saat di mesin saya. Sayangnya, saat ini tidak ada waktu untuk memeriksa log server.

Titus
sumber