# Generate all square sub-matrices of a given size

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

• Sandbox post (now deleted, only users with over 2k reputation can view it). Thanks to everyone who has given feedback. – Mr. Xcoder Feb 9 '18 at 13:27
• So is this output format allowed? – Luis Mendo Feb 9 '18 at 17:55
• @LuisMendo Yes, it is allowed. – Mr. Xcoder Feb 9 '18 at 17:56

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


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

• LOL +1 for "formal, slightly old-fashioned pronoun", and a very nice golf. – Giuseppe Feb 9 '18 at 21:02
• @Giuseppe I just realised it’s a determiner, not a pronoun :-/ – Luis Mendo Feb 10 '18 at 10:04
• Well, I always learned "thy/your" as possessive pronouns; this is my first time hearing of a determiner! – Giuseppe Feb 12 '18 at 15:03
• @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 :-) – Luis Mendo Feb 12 '18 at 15:12

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

• -1 with print -> show – pajonk Jun 17 at 8:03

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

# APL (Dyalog Unicode), 31 bytes

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


Try it online!

• 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) :) – Emigna Feb 9 '18 at 13:45
• @Emigna Yeah, if I have time by then. – Erik the Outgolfer Feb 9 '18 at 13:46
• Very clever. If you can successfully use dyadic ⍉ for non-trivial cases, then you have truly mastered array programming. – Adám Feb 9 '18 at 15:01
• @Adám Uh, although I think this answer is in fact invalid :-( EDIT: Fixed, but now it's 31 bytes long... – Erik the Outgolfer Feb 9 '18 at 15:04
• Feel free to copy the test suite from my submission. – Adám Feb 9 '18 at 15:12

# J, 11 8 bytes

-3 bytes thanks to miles

<;._3~,~


Try it online!

• 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. – miles Feb 10 '18 at 12:30
• @miles Thanks, it's elegant now! – Galen Ivanov Feb 10 '18 at 12:45

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


Try it online!

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

• I suggested something similar to user202729 in chat. An alternative 5-byter is ṡ€Zṡ€. – Mr. Xcoder Feb 9 '18 at 15:37

# 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


# 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│      ┴──┴───┘        ┴──┴───┘
└─┴──┴───┘


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


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

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


# 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!

• 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. – Jonathan Allan Feb 10 '18 at 15:34

# Husk, 8 bytes

TmoTmX¹X


Try it online! This function takes n and M and returns a matrix of matrices.