Jest to dwuwymiarowe uogólnienie tego wyzwania .

Do naszych celów, jeden matrycę (lub panelu 2D) jest uważany za podmatryca innego macierzy B , jeśli może być uzyskany przez całkowite usunięcie liczbę wierszy i kolumn z B . (Uwaga: niektóre źródła mają różne / bardziej restrykcyjne definicje).

Oto przykład:

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]

Możemy usunąć kolumny 2, 3, 5, 6 i wiersze 2, 4 z B, aby uzyskać 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]         _ _ _ _ _ _]

Zauważ, że A jest nadal submatrixem B, jeśli wszystkie wiersze lub wszystkie kolumny B są zachowane (lub w rzeczywistości, jeśli A = B ).

Wyzwanie

Zgadłeś. Biorąc pod uwagę dwa niepusty całkowitą macierzy i B należy określić, czy jest podmatryca z B .

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Dane wejściowe mogą być w dowolnym dogodnym formacie. Macierze można podawać jako listy zagnieżdżone, ciągi znaków z dwoma różnymi separatorami, listy płaskie wraz z wymiarami macierzy itp., O ile dane wejściowe nie są wstępnie przetworzone. Możesz zdecydować się wziąć B najpierw, a A drugi, o ile twój wybór jest zgodny. Możesz założyć, że elementy macierzy są dodatnie i mniejsze niż 256.

Wyjście powinno być zgodne z prawdą, jeśli A jest submatrixem B, a fałsz w przeciwnym razie. Określona wartość wyjściowa nie musi być spójna.

Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

Każdy przypadek testowy jest na osobnej linii A, B.

Prawdziwe przypadki:

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

Przypadki Falsy:

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

Pyth, 10 bajtów

}CQsyMCMyE

Zestaw testowy

Jest to dość proste. Po pierwsze, bierzemy pod uwagę B jako listę wierszy i używamy wszystkich podzbiorów yE. Następnie każda z tych macierzy jest transponowana CMi wszystkie podzbiory są pobierane z ich wierszy, za pomocą yM. Łącząc te podlisty z swszystkimi możliwymi transponowanymi podstronami. Więc transponujemy A za pomocą CQi sprawdzamy, czy jest obecny z }.

Dyalog APL, 53 43 bajty

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

B←⎕, A←⎕Zachęty do Bi A
⍴B, ⍴Awymiary Bi A
/¨replikacji każda, np 2 3/¨4 5→ (4 4) (5 5 5)
⍳¨wszystkie współczynniki w każdym z układów współrzędnych z tych wymiarów
∘.{... }/Tabela możliwych podmatryc, gdzie każdy podmatryca jest zdefiniowane jako wynik funkcji anonimowego {... }stosowanych pomiędzy parą współrzędnych ⍺i ⍵
∧/∊2</¨:jeśli oba ⍺i ⍵są ( ∧/∊) oba ( ¨) zwiększające się ( 2</), to ...
B[⍺;⍵]zwróć podteksty Butworzonych ze skrzyżowań wierszy ⍺i kolumn ⍵
⋄⍬, zwróć pusty wektor (coś, co A nie jest identyczne)
(⊂A)∊⊃sprawdź, czy całość A(⊂A) jest członkiem ∊któregokolwiek z submatrices ( ⊃)

Stare 53-bajtowe rozwiązanie:

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

{… }Anonimowa funkcja wstawiana, w której ⍺argument lewy i kształt ⍵argumentu prawego
⍴, np. 2 3 dla macierzy 2 na 3
(⍴⍺){… }¨⍴⍵dla każdej pary odpowiadających długości wymiarów, zastosuj te anonimowe
⍳⍵*2wskaźniki funkcji kwadratu, tj. 2 → 1 2 3 4
(⍵/2)⊤konwersji binarny (liczba bitów znajduje się wymiar długości kwadratu)
{⍵/⍨⍺=+⌿⍵}stołu binarnej wyboru kolumny ( ⍵/⍨), w których liczba wartości 1 ( +⌿⍵) jest równa długości tego wymiaru potencjalnej podmatryca ( ⍺=)
↓⍉make tabelę do listy kolumn
v h←przechowuj jako v(maski pionowe) i h(maski poziome),
⊣a następnie
h/¨⊂⍵zastosuj każdą maskę poziomą do prawej macierzy argumentów
v∘.⌿zastosuj każdą maskę pionową każdą z poziomo zamaskowanych wersji dużej macierzy,
(⊂⍺)∊sprawdź, czy jej lewą macierz argumentów jest jej członkiem

Galaretka, 12 10 bajtów

Dzięki @Dennis za -2 bajty

ZŒP
ÇÇ€;/i

Prawie taki sam algorytm jak @isaacg, z tym wyjątkiem, że transponujemy macierz przed pobraniem podzbiorów.

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.

Wypróbuj tutaj .

Mathematica, 40 65 bajtów

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

Objaśnienie: Zobacz jedną z pozostałych odpowiedzi - wygląda na to, że wszyscy zrobili to samo.

Brachylog , 4 bajty

⊇z⊇z

Wypróbuj online!

Przeciąga macierz B przez zmienną wejściową, a macierz A przez zmienną wyjściową, i wyprowadza przez sukces lub porażkę. Jest to w zasadzie tylko rozwiązanie Pyth, z wyjątkiem tego, że dane wejściowe są bardziej niejawne i nie ma jawnego generowania ani sprawdzania członkostwa dla zestawów zasilania.

        B
⊇       has a sublist
 z      which transposed
  ⊇     has a sublist
   z    which transposed
        is A.

Haskell, 66 bajtów

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

Przykład użycia: ( (.((s.t=<<).s)).elem.t ) [[149, 221]] [[177, 149, 44, 221]]-> True.

Wersja nie-punktowa to

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

Python + NumPy, 176 173 bajtów

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