20
\$\begingroup\$

This is the 2-dimensional generalisation of this challenge.

For our purposes, one matrix (or 2D array) A is considered a submatrix of another matrix B, if A can be obtained by completely removing a number of rows and columns from B. (Note: some sources have different/more restrictive definitions.)

Here's an example:

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]

We can delete columns 2, 3, 5, 6 and rows 2, 4 from B to obtain 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]         _ _ _ _ _ _]

Note that A is still a submatrix of B if all rows or all columns of B are retained (or in fact if A = B).

The Challenge

You guessed it. Given two non-empty integer matrices A and B, determine if A is a submatrix of B.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input may be in any convenient format. The matrices can be given as nested lists, strings using two different separators, flat lists along with the dimensions of the matrix, etc, as long as the input is not pre-processed. You may choose to take B first and A second, as long as your choice is consistent. You may assume that the elements of the matrices are positive and less then 256.

Output should be truthy if A is a submatrix of B and falsy otherwise. The specific output value does not have to be consistent.

Standard rules apply.

Test Cases

Each test case is on a separate line, A, B.

Truthy cases:

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

Falsy cases:

[[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]]
\$\endgroup\$
3
  • 11
    \$\begingroup\$ I suppose this is a single character in Jelly. \$\endgroup\$
    – Adám
    Mar 9, 2016 at 19:11
  • \$\begingroup\$ @Nᴮᶻ not in APL too? :P \$\endgroup\$
    – Riker
    Mar 10, 2016 at 3:42
  • \$\begingroup\$ @RikerW No, APL only has these and these single character "solutions", while Jelly keeps surprising us with new single character primitives, including most of the leftmost column here... \$\endgroup\$
    – Adám
    Mar 10, 2016 at 13:01

7 Answers 7

7
\$\begingroup\$

Pyth, 10 bytes

}CQsyMCMyE

Test suite

This is fairly straightforward. First, we consider B as a list of rows, and take all subsets using yE. Then, each of those matrices is transposed with CM, and all subsets are taken of their rows, with yM. Concatenating these sublists with s gives all possible transposed submatrices. So we transpose A with CQ, and check if it is present with }.

\$\endgroup\$
6
\$\begingroup\$

Dyalog APL, 53 43 bytes

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

B←⎕, A←⎕prompt for B and A
⍴B, ⍴A dimensions of B and A
replicate each, e.g. 2 3/¨4 5(4 4) (5 5 5)
⍳¨ all indices in each of the coordinate systems with those dimensions
∘.{}/ table of possible submatrices, where each submatrix is defined as the result of the anonymous function {} applied between a pair of coordinates and
∧/∊2</¨: if both and are (∧/∊) both (¨) increasing (2</), then...
B[⍺;⍵] return submatrix of B created from the intersections of rows and columns
⋄⍬ else, return an empty vector (something that A is not identical to)
(⊂A)∊⊃ check if the whole of A (⊂A) is a member of any of the submatrices ()


Old 53-byte solution:

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

{} an anonymous inline function, where is left argument and is right argument
shape, e.g. 2 3 for a 2-by-3 matrix
(⍴⍺){}¨⍴⍵ for each pair of corresponding dimension-lengths, apply this anonymous function
⍳⍵*2 indices of the square of, i.e. 2 → 1 2 3 4
(⍵/2)⊤ convert to binary (number of bits is dimension-length squared)
{⍵/⍨⍺=+⌿⍵} of the binary table, select the columns (⍵/⍨) where the number of 1s (+⌿⍵) is equal to the the length of that dimension in the potential submatrix (⍺=)
↓⍉ make table into list of columns
v h← store as v(ertical masks) and h(horizontal masks)
then
h/¨⊂⍵ apply each horizontal mask to the right argument matrix
v∘.⌿ apply each vertical mask each one of the horizontally masked versions of the large matrix
(⊂⍺)∊ check if the left argument matrix is member thereof

\$\endgroup\$
4
\$\begingroup\$

Jelly, 12 10 bytes

Thanks @Dennis for -2 bytes

ZŒP
ÇÇ€;/i

Nearly the same algorithm as @isaacg, except we transpose the matrix before taking subsets.

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.

Try it here.

\$\endgroup\$
5
  • \$\begingroup\$ Longer than Pyth‽ Impostor! \$\endgroup\$
    – Adám
    Mar 9, 2016 at 20:59
  • 1
    \$\begingroup\$ @Nᴮᶻ I didn't say this was the shortest Jelly solution. \$\endgroup\$
    – lirtosiast
    Mar 9, 2016 at 21:00
  • 1
    \$\begingroup\$ Z at the beginning is shorter than Z}. You can save a further byte by making ZŒP a helper link. \$\endgroup\$
    – Dennis
    Mar 9, 2016 at 21:03
  • \$\begingroup\$ @Dennis Ok, that matches Pyth. Now golf away one more byte. \$\endgroup\$
    – Adám
    Mar 9, 2016 at 21:10
  • \$\begingroup\$ Worth noting that in modern Jelly this is just ZŒP$⁺€Ẏi. \$\endgroup\$ Feb 16, 2022 at 23:40
4
\$\begingroup\$

Brachylog, 4 bytes

⊇z⊇z

Try it online!

Takes matrix B through the input variable and matrix A through the output variable, and outputs through success or failure. This is pretty much just the Pyth solution, except the input is more implicit and there's no explicit generation or membership checking for the powersets.

        B
⊇       has a sublist
 z      which transposed
  ⊇     has a sublist
   z    which transposed
        is A.
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 40 65 bytes

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

Explanation: See one of the other answers -- it looks like they all did the same thing.

\$\endgroup\$
2
\$\begingroup\$

Haskell, 66 bytes

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

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

A non-pointfree version is

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
\$\endgroup\$
0
\$\begingroup\$

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)])
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.