Ini adalah generalisasi 2 dimensi dari tantangan ini .
Untuk tujuan kita, satu matriks (atau array 2D) A dianggap sebagai submatriks lain matriks B , jika A dapat diperoleh dengan melepas sejumlah baris dan kolom dari B . (Catatan: beberapa sumber memiliki definisi yang berbeda / lebih ketat.)
Ini sebuah contoh:
A = [1 4 B = [1 2 3 4 5 6
2 1] 6 5 4 3 2 1
2 1 2 1 2 1
9 1 8 2 7 6]
Kami dapat menghapus kolom 2, 3, 5, 6 dan baris 2, 4 dari B untuk mendapatkan A :
B = [1 2 3 4 5 6 [1 _ _ 4 _ _ [1 4 = A
6 5 4 3 2 1 --> _ _ _ _ _ _ --> 2 1]
2 1 2 1 2 1 2 _ _ 1 _ _
9 1 8 2 7 6] _ _ _ _ _ _]
Perhatikan bahwa A masih merupakan submatrix B jika semua baris atau semua kolom B dipertahankan (atau sebenarnya jika A = B ).
Tantangan
Anda menebaknya. Diberikan dua matriks integer non-kosong A dan B , tentukan apakah A adalah submatrix dari B .
Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter function (out).
Input mungkin dalam format apa pun yang nyaman. Matriks dapat diberikan sebagai daftar bersarang, string menggunakan dua pemisah yang berbeda, daftar datar bersama dengan dimensi matriks, dll., Selama input tidak diproses sebelumnya. Anda dapat memilih untuk mengambil B terlebih dahulu dan A kedua, selama pilihan Anda konsisten. Anda dapat mengasumsikan bahwa unsur-unsur matriks positif dan kurang dari 256.
Output harus truthy jika A adalah submatriks dari B dan falsy sebaliknya. Nilai output spesifik tidak harus konsisten.
Aturan standar kode-golf berlaku.
Uji Kasus
Setiap test case berada pada jalur yang terpisah A, B
,.
Kasus kebenaran:
[[1]], [[1]]
[[149, 221]], [[177, 149, 44, 221]]
[[1, 1, 2], [1, 2, 2]], [[1, 1, 1, 2, 2, 2], [3, 1, 3, 2, 3, 2], [1, 1, 2, 2, 2, 2]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [4, 7, 6], [7, 8, 9], [1, 2, 3], [4, 5, 6], [7, 8, 9]]
[[228, 66], [58, 228]], [[228, 66], [58, 228]]
[[1, 2], [2, 1]], [[1, 2, 2], [2, 1, 2], [2, 2, 1]]
[[136, 196], [252, 136]], [[136, 252, 210, 196, 79, 222], [222, 79, 196, 210, 252, 136], [252, 136, 252, 136, 252, 136], [180, 136, 56, 252, 158, 222]]
Kasus palsu:
[[1]], [[2]]
[[224, 15]], [[144, 15, 12, 224]]
[[41], [150]], [[20, 41, 197, 150]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [7, 8, 9], [4, 5, 6]]
[[1, 2, 2], [2, 1, 2], [2, 2, 1]], [[1, 2], [2, 1]]
[[1, 2, 2], [2, 1, 2]], [[1, 2], [2, 1], [2, 2]]
[[1, 2], [3, 4]], [[5, 3, 4, 5], [2, 5, 5, 1], [4, 5, 5, 3], [5, 1, 2, 5]]
[[158, 112], [211, 211]], [[158, 211, 189, 112, 73, 8], [8, 73, 112, 189, 211, 158], [211, 158, 211, 158, 211, 158], [21, 158, 199, 211, 212, 8]]
sumber
Jawaban:
Pyth, 10 byte
Suite uji
Ini cukup mudah. Pertama, kami menganggap B sebagai daftar baris, dan gunakan semua himpunan bagian
yE
. Kemudian, masing-masing matriks tersebut ditransformasikan denganCM
, dan semua himpunan bagian diambil dari baris mereka, denganyM
. Menggabungkan sublists ini dengans
memberikan semua kemungkinan submatrices yang dialihkan. Jadi kami memindahkan A denganCQ
, dan memeriksa apakah ada}
.sumber
Dyalog APL,
5343 byteB←⎕
,A←⎕
memintaB
danA
⍴B
,⍴A
dimensiB
danA
/¨
mereplikasi masing-masing, misalnya2 3/¨4 5
→(4 4) (5 5 5)
⍳¨
semua indeks di masing-masing sistem koordinat dengan dimensi tersebut∘.{
…}/
tabel kemungkinan pendatang, di mana setiap submatrix didefinisikan sebagai hasil dari fungsi anonim{
...}
diterapkan antara sepasang koordinat⍺
dan⍵
∧/∊2</¨:
jika keduanya⍺
dan⍵
(∧/∊
) keduanya (¨
) meningkat (2</
), maka ...B[⍺;⍵]
kembalikan submatrix yangB
dibuat dari persimpangan baris⍺
dan kolom⍵
⋄⍬
lainnya, kembalikan vektor kosong (sesuatu yang A tidak identik dengan)(⊂A)∊⊃
periksa apakah keseluruhan dariA
(⊂A
) adalah anggota dari∊
salah satu dari para pelarian (⊃
)Solusi 53 byte lama:
{
...}
fungsi inline anonim, di mana⍺
argumen kiri dan bentuk⍵
argumen benar⍴
, misalnya 2 3 untuk matriks 2-by-3(⍴⍺){
...}¨⍴⍵
untuk setiap pasangan panjang dimensi yang sesuai, terapkan⍳⍵*2
indeks fungsi anonim ini dari kuadrat, yaitu 2 → 1 2 3 4(⍵/2)⊤
konversikan ke biner (jumlah bit adalah dimensi-panjang kuadrat){⍵/⍨⍺=+⌿⍵}
dari tabel biner, pilih kolom (⍵/⍨
) di mana jumlah 1s (+⌿⍵
) sama dengan panjang dimensi di potensial submatrix (⍺=
)↓⍉
buat tabel ke dalam daftar kolomv h←
menyimpan sebagaiv
(topeng ertical) danh
(topeng horisontal)⊣
kemudianh/¨⊂⍵
menerapkan setiap topeng horisontal ke matriks argumen yang tepatv∘.⌿
terapkan masing-masing topeng vertikal masing-masing versi yang tertutup secara horizontal dari(⊂⍺)∊
pemeriksaan matriks besar jika matriks argumen kiri adalah anggota daripadanyasumber
Jelly,
1210 byteTerima kasih @Dennis untuk -2 byte
Algoritma hampir sama dengan @isaacg, kecuali kami mengubah urutan matriks sebelum mengambil himpunan bagian.
Coba di sini .
sumber
Z
pada awalnya lebih pendek dariZ}
. Anda dapat menyimpan byte lebih lanjut dengan membuatZŒP
tautan pembantu.Mathematica, 40
65bytePenjelasan: Lihat salah satu jawaban lain - sepertinya mereka semua melakukan hal yang sama.
sumber
Brachylog , 4 byte
Cobalah online!
Membawa matriks B melalui variabel input dan matriks A melalui variabel output, dan output melalui keberhasilan atau kegagalan. Ini cukup banyak hanya solusi Pyth, kecuali inputnya lebih implisit dan tidak ada generasi eksplisit atau keanggotaan yang memeriksa powersets.
sumber
Haskell, 66 byte
Contoh penggunaan:
( (.((s.t=<<).s)).elem.t ) [[149, 221]] [[177, 149, 44, 221]]
->True
.Versi non-pointfree adalah
sumber
Python + NumPy,
176173 bytesumber