Esta es la generalización bidimensional de este desafío .

Para nuestros propósitos, una matriz (o matriz 2D) A se considera una submatriz de otra matriz B , si A se puede obtener mediante la eliminación por completo un número de filas y columnas de B . (Nota: algunas fuentes tienen definiciones diferentes / más restrictivas).

Aquí hay un ejemplo:

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]

Podemos eliminar las columnas 2, 3, 5, 6 y las filas 2, 4 de B para obtener 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]         _ _ _ _ _ _]

Tenga en cuenta que A sigue siendo una submatriz de B si se retienen todas las filas o todas las columnas de B (o, de hecho, si A = B ).

El reto

Lo adivinaste. Dada número entero dos no vacío matrices A y B , determinar si A es una submatriz de B .

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

La entrada puede estar en cualquier formato conveniente. Las matrices se pueden dar como listas anidadas, cadenas que utilizan dos separadores diferentes, listas planas junto con las dimensiones de la matriz, etc., siempre que la entrada no se procese previamente. Puede elegir tomar B primero y A segundo, siempre que su elección sea consistente. Puede suponer que los elementos de las matrices son positivos y menos de 256.

El resultado debe ser verdadero si A es una submatriz de B y falso de lo contrario. El valor de salida específico no tiene que ser consistente.

Aplican reglas estándar de código de golf .

Casos de prueba

Cada caso de prueba está en una línea separada, A, B.

Casos verdaderos:

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

Casos de falsa:

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

}CQsyMCMyE

Banco de pruebas

Esto es bastante sencillo. Primero, consideramos B como una lista de filas, y tomamos todos los subconjuntos usando yE. Luego, cada una de esas matrices se transpone con CM, y todos los subconjuntos se toman de sus filas, con yM. Concatenando estas sublistas con sda todas las submatrices transpuestas posibles. Entonces transponemos A con CQ, y verificamos si está presente con }.

Dyalog APL, 53 43 bytes

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

B←⎕, A←⎕solicitar By A
⍴B, ⍴Adimensiones By A
/¨replicar cada una, por ejemplo, 2 3/¨4 5→ (4 4) (5 5 5)
⍳¨todos los índices en cada uno de los sistemas de coordenadas con esas dimensiones
∘.{... }/tabla de submatrices posibles, donde cada submatriz se define como el resultado de la función anónima {... }aplicada entre un par de coordenadas ⍺y ⍵
∧/∊2</¨:si ambos ⍺y ⍵son ( ∧/∊) ambos ( ¨) aumentando ( 2</), entonces ...
B[⍺;⍵]devuelve la submatriz de Bcreado a partir de las intersecciones de filas ⍺y columnas ⍵
⋄⍬, devuelve un vector vacío (algo con lo que A no es idéntico)
(⊂A)∊⊃verifica si todo A(⊂A) es miembro de ∊cualquiera de las submatrices ( ⊃)

Antigua solución de 53 bytes:

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

{... }una función en línea anónima, donde ⍺está el argumento izquierdo y la forma del ⍵argumento correcto
⍴, por ejemplo, 2 3 para una matriz de 2 por 3
(⍴⍺){... }¨⍴⍵para cada par de longitudes de dimensión correspondientes, aplique estos
⍳⍵*2índices de función anónima del cuadrado de, es decir, 2 → 1 2 3 4
(⍵/2)⊤convertir a binario (número de bits es la dimensión de longitud al cuadrado)
{⍵/⍨⍺=+⌿⍵}de la tabla binaria, seleccionar las columnas ( ⍵/⍨) donde el número de 1s ( +⌿⍵) es igual a la de la longitud de esa dimensión en la submatriz potencial ( ⍺=)
↓⍉make la tabla en la lista de columnas se
v h←almacena como v(máscaras erticales) y h(máscaras horizontales)
⊣luego
h/¨⊂⍵aplique cada máscara horizontal a la matriz de argumento correcta
v∘.⌿aplique cada máscara vertical cada una de las versiones enmascaradas horizontalmente de la matriz grande
(⊂⍺)∊verifique si la matriz del argumento izquierdo es miembro de la misma

Jalea, 12 10 bytes

Gracias @Dennis por -2 bytes

ZŒP
ÇÇ€;/i

Casi el mismo algoritmo que @isaacg, excepto que transponemos la matriz antes de tomar subconjuntos.

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.

Pruébalo aquí .

Mathematica, 40 65 bytes

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

Explicación: Vea una de las otras respuestas, parece que todos hicieron lo mismo.

Brachylog , 4 bytes

⊇z⊇z

Pruébalo en línea!

Toma la matriz B a través de la variable de entrada y la matriz A a través de la variable de salida, y las salidas a través de éxito o fracaso. Esta es prácticamente la solución Pyth, excepto que la entrada es más implícita y no hay una generación explícita o verificación de membresía para los conjuntos de potencia.

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

Haskell, 66 bytes

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

Ejemplo de uso: ( (.((s.t=<<).s)).elem.t ) [[149, 221]] [[177, 149, 44, 221]]-> True.

Una versión sin puntos es

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 bytes

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