Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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]]
share|improve this question
11  
I suppose this is a single character in Jelly. – Adám Mar 9 at 19:11
    
@Nᴮᶻ not in APL too? :P – Eᴀsᴛᴇʀʟʏ Iʀᴋ Mar 10 at 3:42
    
@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... – Adám Mar 10 at 13:01
up vote 6 down vote accepted

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
Longer than Pyth‽ Impostor! – Adám Mar 9 at 20:59
1  
@Nᴮᶻ I didn't say this was the shortest Jelly solution. – lirtosiast Mar 9 at 21:00
1  
Z at the beginning is shorter than Z}. You can save a further byte by making ZŒP a helper link. – Dennis Mar 9 at 21:03
    
@Dennis Ok, that matches Pyth. Now golf away one more byte. – Adám Mar 9 at 21:10

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
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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