Apakah ini submatrix?

21

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 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]]
Martin Ender
sumber
11
Saya kira ini adalah karakter tunggal di Jelly.
Adám
@ Nᴮᶻ tidak di APL juga? : P
Rɪᴋᴇʀ
@RikerW Tidak , APL hanya memiliki ini dan "solusi" karakter tunggal ini , sementara Jelly terus mengejutkan kami dengan primitif karakter tunggal baru, termasuk sebagian besar kolom paling kiri di sini ...
Adám

Jawaban:

7

Pyth, 10 byte

}CQsyMCMyE

Suite uji

Ini cukup mudah. Pertama, kami menganggap B sebagai daftar baris, dan gunakan semua himpunan bagian yE. Kemudian, masing-masing matriks tersebut ditransformasikan dengan CM, dan semua himpunan bagian diambil dari baris mereka, dengan yM. Menggabungkan sublists ini dengan smemberikan semua kemungkinan submatrices yang dialihkan. Jadi kami memindahkan A dengan CQ, dan memeriksa apakah ada }.

isaacg
sumber
6

Dyalog APL, 53 43 byte

(⊂A)∊⊃∘.{∧/∊2</¨⍺⍵:B[⍺;⍵]⋄⍬}/⍳¨(⍴A←⎕)/¨⍴B←⎕

B←⎕, A←⎕meminta Bdan A
⍴B, ⍴Adimensi Bdan A
mereplikasi masing-masing, misalnya 2 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 yang Bdibuat dari persimpangan baris dan kolom
⋄⍬lainnya, kembalikan vektor kosong (sesuatu yang A tidak identik dengan)
(⊂A)∊⊃periksa apakah keseluruhan dariA (⊂A) adalah anggota darisalah satu dari para pelarian ( )


Solusi 53 byte lama:

{(⊂⍺)∊v∘.⌿h/¨⊂⍵⊣v h←(⍴⍺){↓⍉⍺{⍵/⍨⍺=+⌿⍵}(⍵/2)⊤⍳⍵*2}¨⍴⍵}

{... }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
⍳⍵*2indeks 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 kolom
v h←menyimpan sebagai v(topeng ertical) dan h(topeng horisontal)
kemudian
h/¨⊂⍵menerapkan setiap topeng horisontal ke matriks argumen yang tepat
v∘.⌿terapkan masing-masing topeng vertikal masing-masing versi yang tertutup secara horizontal dari
(⊂⍺)∊pemeriksaan matriks besar jika matriks argumen kiri adalah anggota daripadanya

Adm
sumber
3

Jelly, 12 10 byte

Terima kasih @Dennis untuk -2 byte

ZŒP
ÇÇ€;/i

Algoritma hampir sama dengan @isaacg, kecuali kami mengubah urutan matriks sebelum mengambil himpunan bagian.

ZŒP      Helper link. Input: z
Z          Transpose z
ZŒP        All subsets of columns of z.

ÇÇ€;/i   Main link. Input: B, A. B is a list of rows.
Ç          Call the helper link on B. This is the subsequences of columns of A.
 ǀ        Call the helper link on each column-subsequence.
           Now we have a list of lists of submatrices of B.
   ;/      Flatten that once. The list of submatrices of B.
     i     then get the 1-based index of A in that list.
           If A is not in the list, returns 0.

Coba di sini .

lirtosiast
sumber
Lebih panjang dari Penipu Pyth‽!
Adám
1
@ Nᴮᶻ Saya tidak mengatakan ini adalah solusi Jelly terpendek.
lirtosiast
1
Zpada awalnya lebih pendek dari Z}. Anda dapat menyimpan byte lebih lanjut dengan membuat ZŒPtautan pembantu.
Dennis
@ Dennis Ok, itu cocok dengan Pyth. Sekarang golf satu byte lagi.
Adám
3

Mathematica, 40 65 byte

!FreeQ[s[# ]&/@(s=Subsets)@#2,# ]&

Penjelasan: Lihat salah satu jawaban lain - sepertinya mereka semua melakukan hal yang sama.

feersum
sumber
3

Brachylog , 4 byte

⊇z⊇z

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.

        B
⊇       has a sublist
 z      which transposed
  ⊇     has a sublist
   z    which transposed
        is A.
String yang tidak terkait
sumber
1

Haskell, 66 byte

import Data.List
t=transpose
s=subsequences
(.((s.t=<<).s)).elem.t

Contoh penggunaan: ( (.((s.t=<<).s)).elem.t ) [[149, 221]] [[177, 149, 44, 221]]-> True.

Versi non-pointfree adalah

f a b = elem(transpose a) $ (subsequences.transpose=<<) $ subsequences b

                      subsequences b     -- make all subsequences of b, i.e. all 
                                         -- all combinations of rows removed
     (subsequences.transpose=<<)         -- transpose each such sub-matrix and
                                         -- remove rows again. Concatenate into a
                                         -- single list
elem(transpose a)                        -- check if the transposition of a is in
                                         -- the list
nimi
sumber
0

Python + NumPy, 176 173 byte

from itertools import*
from numpy import*
def f(A,B):
 r,c=A.shape
 R,C=B.shape
 S=combinations
 print any([all(B[ix_(i,j)]==A)for i in S(range(R),r)for j in S(range(C),c)])
Karl Napf
sumber