Se le dará una matriz cuadrada de números enteros M y otro número entero positivo n , estrictamente menor que el tamaño de M . Su tarea es generar todas las submatrices cuadradas de M de tamaño n .

Para los fines de este desafío, una sub-matriz cuadrada es un grupo de adyacentes filas y columnas contenida en M .

Formatos de entrada / salida

Usted es libre de elegir cualquier otro formato razonable, estos son solo algunos ejemplos.

Entrada

• Una matriz en el tipo de matriz nativa (si su idioma tiene uno)
• Una matriz 2D (una matriz de matrices 1D, cada una correspondiente a una fila / una columna)
• Una matriz 1D (ya que la matriz siempre es cuadrada)
• Una cadena (elegiste el espacio, pero no abuses de esto de ninguna manera), etc.

Salida

• Una matriz de matrices.
• Una matriz 4D, donde cada elemento (lista 3D) representa las submatrices en una fila / columna.
• Una matriz 3D, donde cada elemento (lista 2D) representa una submatriz.
• Una representación de cadena de las submatrices resultantes, etc.

Especificaciones

• También puede elegir tomar el tamaño de M como entrada. Se garantiza que sea al menos 2 .
• La orientación de la salida es arbitraria: puede optar por generar las submatrices como listas de columnas o listas de filas, pero su elección debe ser coherente.
• Puede competir en cualquier lenguaje de programación y puede tomar entradas y proporcionar salidas a través de cualquier método estándar , mientras toma nota de que estas lagunas están prohibidas por defecto.
• Este es el código de golf , por lo que gana el envío más corto (en bytes) para cada idioma .

Ejemplo

Dado n = 3 y M :

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

Las posibles submatrices 3x3 son:

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

Entonces el resultado sería:

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

Como se señaló anteriormente, una salida de:

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

también sería aceptable si elige devolver las submatrices como listas de filas.

Casos de prueba

Las entradas 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

Y las salidas correspondientes (submatrices dadas como listas de filas):

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

O, como listas de columnas:

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

05AB1E , 8 bytes

2FεŒsù}ø

Pruébalo en línea!

Explicación

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

Las entradas son n, entonces M.

La salida es una matriz, donde cada columna contiene todas las columnas de una submatriz.

Pruébalo en línea!

Explicación

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

Más en serio, ttoma la entrada n implícitamente y la duplica en la pila. hconcatena ambas copias de n , produciendo la matriz [n, n] . YCtoma la entrada M implícitamente, extrae todos sus bloques de tamaño [n, n] y los organiza como columnas en el orden de columnas principales. Esto significa que las columnas de cada bloque se apilan verticalmente para formar una sola columna.

APL (Dyalog Unicode) , ^{SBCS de} 26 bytes

Infix anónimo lambda tomando n como argumento izquierdo y M como argumento derecho.

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

Pruébalo en línea!

{… } Lambda anónima donde ⍺es el argumento izquierdo y ⍵es el argumento correcto:

 ⊢⍵ producir el argumento correcto (se ⊢separa ⍺ ⍺de ⍵)

 ⊢⌺⍺ ⍺ todas ⍺las ⍺submatrices, incluidas las que se superponen a los bordes (se rellenan con ceros)

 (… )↓ Suelte los siguientes elementos numéricos a lo largo de las dos primeras dimensiones:

  ⍺÷2 medio de ⍺

  ¯1+ uno negativo más eso

  ⌈ redondeo

  2⍴ cíclicamente r eshape a una lista de dos elementos

  s← almacenar en s(para s hard)

  - negar (es decir, dejar caer desde la parte trasera)

 s↓soltar selementos a lo largo de la primera y segunda dimensiones (desde el frente)

APL (Dyalog Unicode) , 31 bytes

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

Pruébalo en línea!

Un enfoque diferente al de Adám.

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

Pruébalo en línea!

Toma M, Ny el Stamaño de la matriz.

Imprime las matrices resultantes en stdout; drop=Fes necesario para que, en el N=1caso de que la indexación no elimine el dimatributo y produzca a en matrixlugar de a vector.

J , 11 8 bytes

-3 bytes gracias a millas

<;._3~,~

Pruébalo en línea!

Haskell , 67 bytes

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

Pruébalo en línea!

Jalea , 5 bytes

Z⁹Ƥ⁺€

Utiliza el formato de salida 4D. Para 3D, agregue un Ẏde 6 bytes .

Pruébalo en línea!

Cómo funciona

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.

Brachylog , 13 bytes

{tN&s₎\;Ns₎}ᶠ

Pruébalo en línea!

Esto devuelve listas de columnas.

Técnicamente, tN&s₎\;Ns₎es un predicado generador que unifica su salida con cualquiera de esas submatrices. Usamos {…}ᶠsolo para exponer todas las posibilidades.

Explicación

 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

Stax , 10 bytes

│Æ☼♂Mqß E╖

Ejecutarlo

La representación ascii del mismo programa es

YBFMyBF|PMmJ

Funciona así.

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

JavaScript (ES6), 91 bytes

Toma entrada en la sintaxis de curry (a)(n). Devuelve los resultados como listas de filas.

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)

Casos de prueba

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

APL (Dyalog Classic) , 24 23 bytes

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

Pruébalo en línea!

el resultado es una matriz de matrices, aunque el formato de salida de Dyalog no lo hace muy obvio

ingrese la matriz ( ⎕), convierta cada elemento en una matriz anidada propia ( ⍪¨), tome concatenaciones de prefijo por fila ( ,\) y por columna ( ⍪⍀), ingrese n ( ⎕), suelte las primeras filas n-1 y columnas de matrices anidadas ( (¯1-t←-2⍴⎕)↓), tome la esquina inferior derecha n-por-n de cada matriz ( 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│      ┴──┴───┘        ┴──┴───┘
                                        └─┴──┴───┘

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

Pruébalo en línea!

Esta es una lambda que toma una matriz 2D y una int, devolviendo una matriz 3D.

Sin golf:

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

Pruébalo en línea!