Ist das eine Submatrix?

21

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 .

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]]
Martin Ender
quelle
11
Ich nehme an, das ist eine einzelne Figur in Jelly.
Adám
@Nicht auch in APL? : P
Rɪᴋᴇʀ
@RikerW Nein , APL hat nur diese und diese Einzelzeichen-"Lösungen", während Jelly uns immer wieder mit neuen Einzelzeichen-Primitiven überrascht, einschließlich des größten
Adám

Antworten:

7

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 }.

isaacg
quelle
6

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

Adam
quelle
3

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 .

Lirtosiast
quelle
Länger als Pyth‽ Impostor!
Adám
1
@ Nᴮᶻ Ich habe nicht gesagt, dass dies die kürzeste Jelly-Lösung ist.
Lirtosiast
1
Zam anfang ist kürzer als Z}. Sie können ein weiteres Byte speichern, indem Sie ZŒPeinen Hilfslink erstellen.
Dennis
@ Tennis Ok, das passt zu Pyth. Jetzt noch ein Byte weiterspielen.
Adám
3

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.

Feersum
quelle
3

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.
Nicht verwandte Zeichenfolge
quelle
1

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
nimi
quelle
0

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)])
Karl Napf
quelle