14
\$\begingroup\$

You will be given a square matrix of integers M and another positive integer n, strictly smaller than the size of M. Your task is to generate all square sub-matrices of M of size n.

For the purposes of this challenge, a square sub-matrix is a group of adjacent rows and columns contained in M.

Input / Output Formats

You are free to choose any other reasonable formats, these are just some examples.

Input

  • A matrix in the native matrix type (if your language has one)
  • A 2D array (an array of 1D arrays, each corresponding to one row / one column)
  • A 1D array (since the matrix is always square)
  • A string (you chose the spacing, but please do not abuse this in any way), etc.

Output

  • A matrix of matrices.
  • A 4D array, where each element (3D list) represents the sub-matrices on a row/column.
  • A 3D array, where each element (2D list) represents a sub-matrix.
  • A string representation of the resulting sub-matrices, etc.

Specs

  • You may choose to take the size of M as input too. It is guaranteed to be at least 2.
  • The orientation of the output is arbitrary: you may choose to output the sub-matrices as lists of columns or lists of rows, but your choice must be consistent.
  • You can compete in any programming language and can take input and provide output through any standard method, while taking note that these loopholes are forbidden by default.
  • This is , so the shortest submission (in bytes) for every language wins.

Example

Given n = 3 and M:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

The possible 3x3 submatrices are:

+-------+        +--------+     1  2  3  4         1  2  3  4
|1  2  3| 4     1| 2  3 4 |     +--------+         +--------+
|5  6  7| 8     5| 6  7 8 |     |5   6  7|8       5| 6  7  8|
|9 10 11|12     9|10 11 12|     |9  10 11|12      9|10 11 12|
+-------+        +--------+     |13 14 15|16     13|14 15 16|
13 14 15 16     13 14 15 16     +--------+         +--------+

So the result would be:

[[[1, 2, 3], [5, 6, 7], [9, 10, 11]], [[2, 3, 4], [6, 7, 8], [10, 11, 12]], [[5, 6, 7], [9, 10, 11], [13, 14, 15]], [[6, 7, 8], [10, 11, 12], [14, 15, 16]]]

As noted above, an output of:

[[[1, 5, 9], [2, 6, 10], [3, 7, 11]], [[2, 6, 10], [3, 7, 11], [4, 8, 12]], [[5, 9, 13], [6, 10, 14], [7, 11, 15]], [[6, 10, 14], [7, 11, 15], [8, 12, 16]]]

would also be acceptable, if you choose to return the sub-matrices as lists of rows instead.

Test cases

The inputs M, n:

[[1,2,3],[5,6,7],[9,10,11]], 1
[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], 3
[[100,-3,4,6],[12,11,14,8],[0,0,9,3],[34,289,-18,3]], 2
[[100,-3,4,6],[12,11,14,8],[9,10,11,12],[13,14,15,16]], 3

And the corresponding outputs (sub-matrices given as lists of rows):

[[[1]],[[2]],[[3]],[[5]],[[6]],[[7]],[[9]],[[10]],[[11]]]
[[[1,2,3],[5,6,7],[9,10,11]],[[2,3,4],[6,7,8],[10,11,12]],[[5,6,7],[9,10,11],[13,14,15]],[[6,7,8],[10,11,12],[14,15,16]]]
[[[100,-3],[12,11]],[[-3,4],[11,14]],[[4,6],[14,8]],[[12,11],[0,0]],[[11,14],[0,9]],[[14,8],[9,3]],[[0,0],[34,289]],[[0,9],[289,-18]],[[9,3],[-18,3]]]
[[[100,-3,4],[12,11,14],[9,10,11]],[[-3,4,6],[11,14,8],[10,11,12]],[[12,11,14],[9,10,11],[13,14,15]],[[11,14,8],[10,11,12],[14,15,16]]]

Or, as lists of columns:

[[[1]],[[2]],[[3]],[[5]],[[6]],[[7]],[[9]],[[10]],[[11]]]
[[[1,5,9],[2,6,10],[3,7,11]],[[2,6,10],[3,7,11],[4,8,12]],[[5,9,13],[6,10,14],[7,11,15]],[[6,10,14],[7,11,15],[8,12,16]]]
[[[100,12],[-3,11]],[[-3,11],[4,14]],[[4,14],[6,8]],[[12,0],[11,0]],[[11,0],[14,9]],[[14,9],[8,3]],[[0,34],[0,289]],[[0,289],[9,-18]],[[9,-18],[3,3]]]
[[[100,12,9],[-3,11,10],[4,14,11]],[[-3,11,10],[4,14,11],[6,8,12]],[[12,9,13],[11,10,14],[14,11,15]],[[11,10,14],[14,11,15],[8,12,16]]]]
\$\endgroup\$
  • \$\begingroup\$ Sandbox post (now deleted, only users with over 2k reputation can view it). Thanks to everyone who has given feedback. \$\endgroup\$ – Mr. Xcoder Feb 9 '18 at 13:27
  • \$\begingroup\$ So is this output format allowed? \$\endgroup\$ – Luis Mendo Feb 9 '18 at 17:55
  • \$\begingroup\$ @LuisMendo Yes, it is allowed. \$\endgroup\$ – Mr. Xcoder Feb 9 '18 at 17:56

14 Answers 14

5
\$\begingroup\$

05AB1E, 8 bytes

2FεŒsù}ø

Try it online!

Explanation

2F            # 2 times do:
  ε    }      # apply to each element in the input matrix (initially rows)
   Œsù        # get a list of sublists of size input_2
        ø     # transpose (handling columns on the second pass of the loop)
\$\endgroup\$
5
\$\begingroup\$

MATL, 4 bytes

thYC

Inputs are n, then M.

The output is a matrix, where each column contains all the columns of a submatrix.

Try it online!

Explanation

thY    % Address the compiler with a formal, slightly old-fashioned determiner
C      % Convert input to ouput

More seriously, t takes input n implictly and duplicates it on the stack. h concatenates both copies of n, producing the array [n, n]. YC takes input M implicitly, extracts all its [n, n]-size blocks, and arranges them as columns in column-major order. This means that the columns of each block are stacked vertically to form a single column.

\$\endgroup\$
  • 1
    \$\begingroup\$ LOL +1 for "formal, slightly old-fashioned pronoun", and a very nice golf. \$\endgroup\$ – Giuseppe Feb 9 '18 at 21:02
  • \$\begingroup\$ @Giuseppe I just realised it’s a determiner, not a pronoun :-/ \$\endgroup\$ – Luis Mendo Feb 10 '18 at 10:04
  • \$\begingroup\$ Well, I always learned "thy/your" as possessive pronouns; this is my first time hearing of a determiner! \$\endgroup\$ – Giuseppe Feb 12 '18 at 15:03
  • \$\begingroup\$ @Giuseppe "Thy/your" are possessive determiners, that is, they go with a name: "This is your car". "Thine/yours" are possessive pronouns, that is, the name is omitted: "This is yours". And I initially confused "thy" with a personal pronoun, which would actually be "thou". What a mess I've made :-) \$\endgroup\$ – Luis Mendo Feb 12 '18 at 15:12
4
\$\begingroup\$

APL (Dyalog Unicode), 26 bytesSBCS

Anonymous infix lambda taking n as left argument and M as right argument.

{s↓(-s←2⍴⌈¯1+⍺÷2)↓⊢⌺⍺ ⍺⊢⍵}

Try it online!

{} anonymous lambda where is the left argument and is the right argument:

⊢⍵ yield the right argument ( separates ⍺ ⍺ from )

⊢⌺⍺ ⍺ all -by- submatrices including those overlapping the edges (those are padded with zeros)

()↓ drop the following number elements along the first two dimensions:

  ⍺÷2 half of

  ¯1+ negative one plus that

   round up

  2⍴ cyclically reshape to a list of two elements

  s← store in s (for shards)

  - negate (i.e. drop from the rear)

s↓ drop s elements along the first and second dimensions (from the front)

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

APL (Dyalog Unicode), 31 bytes

{(1↓2 1 3 4⍉⊖)⍣(4×⌊⍺÷2)⊢⌺⍺ ⍺⊢⍵}

Try it online!

A different approach than Adám's.

\$\endgroup\$
  • \$\begingroup\$ Do you intend to provide an explanation (after you've finished golfing of course)? I'd be interested to see how it works (and I don't know APL at all) :) \$\endgroup\$ – Emigna Feb 9 '18 at 13:45
  • \$\begingroup\$ @Emigna Yeah, if I have time by then. \$\endgroup\$ – Erik the Outgolfer Feb 9 '18 at 13:46
  • \$\begingroup\$ Very clever. If you can successfully use dyadic for non-trivial cases, then you have truly mastered array programming. \$\endgroup\$ – Adám Feb 9 '18 at 15:01
  • \$\begingroup\$ @Adám Uh, although I think this answer is in fact invalid :-( EDIT: Fixed, but now it's 31 bytes long... \$\endgroup\$ – Erik the Outgolfer Feb 9 '18 at 15:04
  • \$\begingroup\$ Feel free to copy the test suite from my submission. \$\endgroup\$ – Adám Feb 9 '18 at 15:12
3
\$\begingroup\$

R, 75 bytes

function(M,N,S,W=1:N,g=N:S-N)for(i in g)for(j in g)print(M[i+W,j+W,drop=F])

Try it online!

Takes M, N, and the Size of the matrix.

Prints the resultant matrices to stdout; drop=F is needed so the in the N=1 case the indexing doesn't drop the dim attribute and yields a matrix rather than a vector.

\$\endgroup\$
3
\$\begingroup\$

J, 11 8 bytes

-3 bytes thanks to miles

<;._3~,~

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ This uses 8 bytes <;._3~,~ and uses a hook instead to pair the size with itself, then cuts and boxes each since a matrix of matrices is allowed as output. \$\endgroup\$ – miles Feb 10 '18 at 12:30
  • \$\begingroup\$ @miles Thanks, it's elegant now! \$\endgroup\$ – Galen Ivanov Feb 10 '18 at 12:45
2
\$\begingroup\$

Haskell, 67 bytes

m#n|r<-[0..length m-n]=[take n.drop x<$>take n(drop y m)|x<-r,y<-r]

Try it online!

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

Jelly, 5 bytes

Z⁹Ƥ⁺€

Uses the 4D output format. For 3D, append a for 6 bytes.

Try it online!

How it works

Z⁹Ƥ⁺€  Main link. Left argument: M (matrix). Right argument: n (integer)

 ⁹Ƥ    Apply the link to the left to all infixes of length n.
Z        Zip the rows of the infix, transposing rows and columns.
   ⁺€  Map Z⁹Ƥ over all results.
\$\endgroup\$
  • \$\begingroup\$ I suggested something similar to user202729 in chat. An alternative 5-byter is ṡ€Zṡ€. \$\endgroup\$ – Mr. Xcoder Feb 9 '18 at 15:37
2
\$\begingroup\$

Brachylog, 13 bytes

{tN&s₎\;Ns₎}ᶠ

Try it online!

This returns lists of columns.

Technically, tN&s₎\;Ns₎ is a generating predicate which unifies its output with any of those submatrices. We use {…}ᶠ only to expose all possibilities.

Explanation

 tN&              Call the second argument of the input N
{          }ᶠ     Find all:
    s₎              A substring of the matrix of size N
      \             Transpose that substring
       ;Ns₎         A substring of that transposed substring of size N
\$\endgroup\$
1
\$\begingroup\$

Stax, 10 bytes

│Æ☼♂Mqß E╖

Run it

The ascii representation of the same program is

YBFMyBF|PMmJ

It works like this.

Y               Store the number in the y register
 B              Batch the grid into y rows each
  F             Foreach batch, run the rest of the program
   M            Transpose about the diagonal
    yB          Batch the transposed slices into y rows each
      F         Foreach batch, run the rest of the progoram
       |P       Print a blank line
         M      Transpose inner slice - restoring its original orientation
          mJ    For each row in the inner grid, output joined by spaces
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 91 bytes

Takes input in currying syntax (a)(n). Returns the results as lists of rows.

a=>n=>(g=x=>a[y+n-1]?[a.slice(y,y+n).map(r=>r.slice(x,x+n)),...g(a[x+n]?x+1:!++y)]:[])(y=0)

Test cases

let f =

a=>n=>(g=x=>a[y+n-1]?[a.slice(y,y+n).map(r=>r.slice(x,x+n)),...g(a[x+n]?x+1:!++y)]:[])(y=0)

;[
  [ [[1,2,3],[5,6,7],[9,10,11]], 1 ],
  [ [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], 3 ],
  [ [[100,-3,4,6],[12,11,14,8],[0,0,9,3],[34,289,-18,3]], 2 ],
  [ [[100,-3,4,6],[12,11,14,8],[9,10,11,12],[13,14,15,16]], 3]
]
.forEach(([m, a]) => console.log(JSON.stringify(f(m)(a))))

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Classic), 24 23 bytes

t∘↑¨(¯1-t←-2⍴⎕)↓,⍀⍪\⍪¨⎕

Try it online!

the result is a matrix of matrices, though Dyalog's output formatting doesn't make that very obvious

input the matrix (), turn each element into a nested matrix of its own (⍪¨), take prefix concatenations by row (,\) and by column (⍪⍀), input n (), drop the first n-1 rows and columns of nested matrices ((¯1-t←-2⍴⎕)↓), take the bottom right n-by-n corner from each matrix (t∘↑¨)

                                        ┌─┬──┬───┐
                                        │a│ab│abc│      ┼──┼───┤        ┼──┼───┤
 n=2       ┌─┬─┬─┐      ┌─┬──┬───┐      ├─┼──┼───┤      │ab│abc│        │ab│ bc│
┌───┐      │a│b│c│      │a│ab│bac│      │a│ab│abc│      │de│def│        │de│ ef│
│abc│  ⍪¨  ├─┼─┼─┤  ,\  ├─┼──┼───┤  ⍪⍀  │d│de│def│ 1 1↓ ┼──┼───┤¯2 ¯2∘↑¨┼──┼───┤
│def│ ---> │d│e│f│ ---> │d│de│edf│ ---> ├─┼──┼───┤ ---> │ab│abc│  --->  │  │   │
│ghi│      ├─┼─┼─┤      ├─┼──┼───┤      │a│ab│abc│      │de│def│        │de│ ef│
└───┘      │g│h│i│      │g│gh│hgi│      │d│de│def│      │gh│ghi│        │gh│ hi│
           └─┴─┴─┘      └─┴──┴───┘      │g│gh│ghi│      ┴──┴───┘        ┴──┴───┘
                                        └─┴──┴───┘
\$\endgroup\$
0
\$\begingroup\$

Ruby, 63 bytes

->c,g{n=c.size-g+1
(0...n*n).map{|i|c[i/n,g].map{|z|z[i%n,g]}}}

Try it online!

This is a lambda taking a 2D array and an int, returning a 3D array.

Ungolfed:

->m,n{
  a = m.size - n + 1     # The count of rows in m that can be a first row in a submatrix
  (0...a*a).map{ |b|     # There will be a*a submatrices
    m[b/a,n].map{ |r|    # Take each possible set of n rows
      r[b%a,n]           # And each possible set of n columns
    }
  }
}
\$\endgroup\$
0
\$\begingroup\$

Python 2, 91 bytes

lambda a,n:(lambda R:[[r[i:i+n]for r in a[j:j+n]]for i in R for j in R])(range(len(a)+1-n))

Try it online!

\$\endgroup\$
  • \$\begingroup\$ def f(a,n):R=range(len(a)+1-n);print[[r[i:i+n]for r in a[j:j+n]]for i in R for j in R] saves five. \$\endgroup\$ – Jonathan Allan Feb 10 '18 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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