Dies ist die zweidimensionale Verallgemeinerung dieser Herausforderung .

Für unsere Zwecke wird eine Matrix (oder ein 2D-Array) A als Submatrix einer anderen Matrix B betrachtet , wenn A erhalten werden kann, indem eine Anzahl von Zeilen und Spalten vollständig aus B entfernt wird . (Hinweis: Einige Quellen haben andere / restriktivere Definitionen.)

Hier ist ein Beispiel:

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]

Wir können die Spalten 2, 3, 5, 6 und die Zeilen 2, 4 aus B löschen , um A zu erhalten :

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

Beachten Sie, dass A immer noch eine Submatrix von B ist, wenn alle Zeilen oder alle Spalten von B beibehalten werden (oder tatsächlich, wenn A = B ist ).

Die Herausforderung

Du hast es erraten. Bestimmen Sie bei zwei nicht leeren ganzzahligen Matrizen A und B , ob A eine Untermatrix von B ist .

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Die Eingabe kann in einem beliebigen Format erfolgen. Die Matrizen können als verschachtelte Listen, Zeichenfolgen mit zwei verschiedenen Trennzeichen, flache Listen zusammen mit den Abmessungen der Matrix usw. angegeben werden, solange die Eingabe nicht vorverarbeitet wird. Sie können B als erstes und A als zweites wählen , solange Ihre Wahl konsistent ist. Sie können annehmen, dass die Elemente der Matrizen positiv und kleiner als 256 sind.

Die Ausgabe sollte wahr sein, wenn A eine Submatrix von B ist und ansonsten falsch . Der spezifische Ausgabewert muss nicht konsistent sein.

Es gelten die Standardregeln für Code-Golf .

Testfälle

Jeder Testfall befindet sich in einer separaten Zeile A, B.

Wahrheitsfälle:

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

Falsche Fälle:

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

Testsuite

Das ist ziemlich einfach. Zunächst betrachten wir B als eine Liste von Zeilen und nehmen alle Teilmengen mit yE. Dann wird jede dieser Matrizen mit transponiert CM, und alle Teilmengen werden mit von ihren Zeilen genommen yM. Die Verkettung dieser Unterlisten mit sergibt alle möglichen transponierten Untermatrizen. Also transponieren wir A mit CQund prüfen, ob es mit vorhanden ist }.

Dyalog APL, 53 43 Bytes

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

B←⎕, A←⎕Aufforderung zur Eingabe Bund A
⍴B, ⍴ADimensionen Bund A
/¨replizieren jeweils, zB 2 3/¨4 5→ (4 4) (5 5 5)
⍳¨alle Indizes in jedem der Koordinatensysteme mit den Abmessungen
∘.{... }/Tabelle möglicher Teilmatrizen, wobei jede Untermatrix als Ergebnis der anonymen Funktion definiert ist {... }zwischen einem Paar von Koordinaten aufgetragen ⍺und ⍵
∧/∊2</¨:Wenn beide ⍺und ⍵( ∧/∊) beide ( ¨) zunehmen ( 2</), dann ...
B[⍺;⍵]Submatrix Baus den Schnittpunkten von Zeilen ⍺und Spalten zurückgeben, ⍵
⋄⍬sonst einen leeren Vektor zurückgeben (etwas, mit dem A nicht identisch ist),
(⊂A)∊⊃prüfen Sie, ob die gesamte A(⊂A) ist Mitglied ∊einer der Submatrizen ( ⊃)

Alte 53-Byte-Lösung:

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

{... }eine anonyme Inline-Funktion, bei der ⍺das linke Argument und ⍵das rechte Argument die
⍴Form haben, z. B. 2 3 für eine 2 × 3-Matrix
(⍴⍺){... Wenden Sie }¨⍴⍵für jedes Paar entsprechender Dimensionslängen diese anonymen Funktionsindizes
⍳⍵*2des Quadrats von, dh 2 → an 1 2 3 4
(⍵/2)⊤Umrechnen in binärem (Anzahl der Bits sind dimensions Länge zum Quadrat)
{⍵/⍨⍺=+⌿⍵}der binären Tabelle, die Spalten auswählen ( ⍵/⍨) , in dem die Anzahl der 1en ( +⌿⍵) an der der Länge dieser Dimension in dem Potential Submatrix gleich ( ⍺=)
↓⍉make Tabelle in Spaltenliste
v h←speichern als v(vertikale Masken) und h(horizontale Masken),
⊣dann
h/¨⊂⍵jede horizontale Maske auf die rechte Argumentmatrix anwenden
v∘.⌿Wenden Sie für jede vertikale Maske eine der horizontal maskierten Versionen der großen Matrixprüfung an
(⊂⍺)∊, wenn die linke Argumentmatrix Mitglied davon ist

Gelee, 12 10 Bytes

Danke @Dennis für -2 Bytes

ZŒP
ÇÇ€;/i

Fast der gleiche Algorithmus wie @isaacg, außer dass wir die Matrix transponieren, bevor wir Teilmengen nehmen.

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.

Probieren Sie es hier aus .

Mathematica, 40-65 Bytes

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

Erläuterung: Sehen Sie sich eine der anderen Antworten an - es sieht so aus, als hätten alle dasselbe getan.

Brachylog , 4 Bytes

⊇z⊇z

Probieren Sie es online!

Nimmt Matrix B durch die Eingabevariable und Matrix A durch die Ausgabevariable und gibt sie durch Erfolg oder Misserfolg aus. Dies ist so ziemlich nur die Pyth-Lösung, außer dass die Eingabe impliziter ist und es keine explizite Generierung oder Zugehörigkeitsprüfung für die Powersets gibt.

        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

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

Eine nicht pointfree Version ist

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