Generieren Sie alle quadratischen Submatrizen einer bestimmten Größe

14

Sie erhalten eine quadratische Matrix aus ganzen Zahlen M und eine weitere positive ganze Zahl n , die genau kleiner als die Größe von M ist . Ihre Aufgabe ist es, alle quadratischen Teilmatrizen von M der Größe n zu erzeugen .

Für die Zwecke dieser Herausforderung ist eine quadratische Untermatrix eine Gruppe benachbarter Zeilen und Spalten, die in M enthalten sind .

Eingabe- / Ausgabeformate

Es steht Ihnen frei, ein anderes vernünftiges Format zu wählen. Dies sind nur einige Beispiele.

Eingang

  • Eine Matrix im nativen Matrixtyp (falls Ihre Sprache eine hat)
  • Ein 2D-Array (ein Array von 1D-Arrays, die jeweils einer Zeile / einer Spalte entsprechen)
  • Ein 1D-Array (da die Matrix immer quadratisch ist)
  • Eine Zeichenkette (Sie haben den Abstand gewählt, aber bitte missbrauchen Sie diesen in keiner Weise) usw.

Ausgabe

  • Eine Matrix von Matrizen.
  • Ein 4D Array, bei dem jedes Element (3D Liste) die Untermatrizen einer Zeile / Spalte darstellt.
  • Ein 3D-Array, bei dem jedes Element (2D-Liste) eine Untermatrix darstellt.
  • Eine Zeichenfolgendarstellung der resultierenden Untermatrizen usw.

Technische Daten

  • Sie können auch die Größe von M als Eingabe verwenden. Es ist garantiert mindestens 2 .
  • Die Ausrichtung der Ausgabe ist beliebig: Sie können festlegen, dass die Untermatrizen als Listen von Spalten oder Zeilen ausgegeben werden. Ihre Auswahl muss jedoch konsistent sein.
  • Sie können sich in jeder Programmiersprache messen und über jede Standardmethode Eingaben und Ausgaben vornehmen , wobei Sie diese Lücken beachten müssen standardmäßig verboten sind.
  • Dies ist , daher gewinnt die kürzeste Übermittlung (in Bytes) für jede Sprache .

Beispiel

Bei n = 3 und M :

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

Die möglichen 3x3- Submatrizen sind:

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

Das Ergebnis wäre also:

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

Wie oben erwähnt, eine Ausgabe von:

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

Dies ist auch akzeptabel, wenn Sie die Untermatrizen stattdessen als Zeilenlisten zurückgeben.

Testfälle

Die Eingänge 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

Und die entsprechenden Ausgaben (Submatrizen als Zeilenlisten):

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

Oder als Spaltenliste:

[[[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]]]]
Mr. Xcoder
quelle
Sandbox-Post (jetzt gelöscht, nur Benutzer mit mehr als 2.000 Reputation können ihn anzeigen). Vielen Dank an alle, die Feedback gegeben haben.
Mr. Xcoder
Ist dieses Ausgabeformat also zulässig?
Luis Mendo
@ LuisMendo Ja, es ist erlaubt.
Mr. Xcoder

Antworten:

6

05AB1E , 8 Bytes

2FεŒsù}ø

Probieren Sie es online!

Erläuterung

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)
Emigna
quelle
5

MATL , 4 Bytes

thYC

Eingänge sind ndann M.

Die Ausgabe ist eine Matrix, in der jede Spalte alle Spalten einer Untermatrix enthält.

Probieren Sie es online!

Erläuterung

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

Mehr ernst, tnimmt die Eingabe n implizit und dupliziert es auf dem Stapel. hverkettet beide Kopien von n und erzeugt das Array [n, n] . Nimmt implizit YCdie Eingabe M , extrahiert alle ihre [n, n] -Größenblöcke und ordnet sie als Spalten in der Hauptreihenfolge der Spalten an. Dies bedeutet, dass die Spalten jedes Blocks vertikal gestapelt sind, um eine einzelne Spalte zu bilden.

Luis Mendo
quelle
1
LOL +1 für "formales, leicht altmodisches Pronomen" und ein sehr schönes Golf.
Giuseppe
@ Giuseppe Ich habe gerade festgestellt, es ist ein Determinator, kein Pronomen: - /
Luis Mendo
Nun, ich habe immer "dein" als Possessivpronomen gelernt; Ich höre zum ersten Mal einen Bestimmer!
Giuseppe
@ Giuseppe "Deine / Deine" sind besitzergreifende Determinanten, das heißt, sie gehen mit einem Namen einher: "Das ist dein Auto". "Dein" sind Possessivpronomen, dh der Name wird weggelassen: "Das ist dein". Und ich habe anfangs "dein" mit einem Personalpronomen verwechselt, das eigentlich "du" wäre. Was für ein Durcheinander habe ich gemacht :-)
Luis Mendo
4

APL (Dyalog Unicode) , 26 Byte SBCS

Anonymes Infix Lambda mit n als linkem Argument und M als rechtem Argument.

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

Probieren Sie es online!

{... } anonymes Lambda, wobei das linke und das rechte Argument ist:

⊢⍵ das richtige Argument liefern ( trennt⍺ ⍺ von )

⊢⌺⍺ ⍺ alle -by- einschließlich derjenigen, die die Kanten überlappen (diese sind mit Nullen aufgefüllt)

()↓  Lassen Sie die folgenden Zahlenelemente entlang der ersten beiden Dimensionen fallen:

  ⍺÷2 die Hälfte von

  ¯1+ negative eins plus das

   zusammenfassen

  2⍴ zyklisch r eshape auf eine Liste von zwei Elementen

  s← in s(für s hards)

  - negieren (dh von hinten fallen lassen)

s↓Drop- sElemente entlang der ersten und zweiten Dimension (von vorne)

Adam
quelle
4

APL (Dyalog Unicode) , 31 Byte

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

Probieren Sie es online!

Ein anderer Ansatz als bei Adám.

Erik der Outgolfer
quelle
Haben Sie vor, eine Erklärung abzugeben (nachdem Sie das Golfen beendet haben)? Es würde mich interessieren, wie es funktioniert (und ich kenne APL überhaupt nicht) :)
Emigna
@Emigna Ja, wenn ich bis dahin Zeit habe.
Erik der Outgolfer
Sehr schlau. Wenn Sie dyadic erfolgreich für nicht-triviale Fälle einsetzen können, haben Sie die Array-Programmierung wirklich beherrscht.
Adám
@ Adám Uh, obwohl ich denke, dass diese Antwort in der Tat ungültig ist :-( BEARBEITEN: Behoben, aber jetzt ist es 31 Bytes lang ...
Erik der Outgolfer
Fühlen Sie sich frei, die Testsuite von meinem Beitrag zu kopieren.
Adám
3

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

Probieren Sie es online!

Takes M,N und das SIze der Matrix.

Druckt die resultierenden Matrizen auf stdout. drop=Fwird benötigt, damit in dem N=1Fall, in dem die Indizierung das dimAttribut nicht löscht und a matrixstatt a ergibt vector.

Giuseppe
quelle
3

J , 11 8 Bytes

-3 Bytes dank Meilen

<;._3~,~

Probieren Sie es online!

Galen Ivanov
quelle
1
Dies verwendet 8 Bytes <;._3~,~und verwendet stattdessen einen Haken, um die Größe mit sich selbst zu koppeln. Anschließend werden jeweils Schnitte und Kästchen eingefügt, da eine Matrix von Matrizen als Ausgabe zulässig ist.
Meilen
@miles Danke, es ist jetzt elegant!
Galen Ivanov
2

Gelee , 5 Bytes

Z⁹Ƥ⁺€

Verwendet das 4D Ausgabeformat. Fügen Sie für 3D ein für 6 Bytes an .

Probieren Sie es online!

Wie es funktioniert

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.
Dennis
quelle
Ich habe im Chat etwas Ähnliches wie user202729 vorgeschlagen. Eine alternative 5-Byte ist ṡ€Zṡ€.
Mr. Xcoder
2

Brachylog , 13 Bytes

{tN&s₎\;Ns₎}ᶠ

Probieren Sie es online!

Dies gibt Listen von Spalten zurück.

Technisch gesehen tN&s₎\;Ns₎ist es ein generierendes Prädikat, das seine Ausgabe mit einer dieser Submatrizen vereinheitlicht. Wir gebrauchen{…}ᶠ nur, um alle Möglichkeiten aufzudecken.

Erläuterung

 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
Tödlich
quelle
1

Stax , 10 Bytes

│Æ☼♂Mqß E╖

Starte es

Die ASCII-Darstellung des gleichen Programms ist

YBFMyBF|PMmJ

Das funktioniert so.

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
rekursiv
quelle
1

JavaScript (ES6), 91 Byte

Übernimmt Eingaben in der Currying-Syntax (a)(n). Gibt die Ergebnisse als Zeilenlisten zurück.

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)

Testfälle

Arnauld
quelle
1

APL (Dyalog Classic) , 24 23 Bytes

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

Probieren Sie es online!

Das Ergebnis ist eine Matrix aus Matrizen, obwohl die Ausgabeformatierung von Dyalog dies nicht sehr offensichtlich macht

Geben Sie die Matrix ( ) ein, verwandeln Sie jedes Element in eine eigene verschachtelte Matrix ( ⍪¨), nehmen Sie Präfixverkettungen nach Zeile ( ,\) und nach Spalte ( ⍪⍀) vor, geben Sie n ( ) ein und löschen Sie die ersten n-1 Zeilen und Spalten verschachtelter Matrizen ( (¯1-t←-2⍴⎕)↓), nimm die rechte untere n-mal-n-Ecke von jeder Matrix ( t∘↑¨)

                                        ┌─┬──┬───┐
                                        aababc      ┼──┼───┤        ┼──┼───┤
 n=2       ┌─┬─┬─┐      ┌─┬──┬───┐      ├─┼──┼───┤      ababc        ab bc
┌───┐      abc      aabbac      aababc      dedef        de ef
abc  ⍪¨  ├─┼─┼─┤  ,\  ├─┼──┼───┤  ⍪⍀  ddedef 1 1 ┼──┼───┤¯2 ¯2∘↑¨┼──┼───┤
def ---> def ---> ddeedf ---> ├─┼──┼───┤ ---> ababc  --->       
ghi      ├─┼─┼─┤      ├─┼──┼───┤      aababc      dedef        de ef
└───┘      ghi      gghhgi      ddedef      ghghi        gh hi
           └─┴─┴─┘      └─┴──┴───┘      gghghi      ┴──┴───┘        ┴──┴───┘
                                        └─┴──┴───┘
ngn
quelle
0

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

Probieren Sie es online!

Dies ist ein Lambda, das ein 2D-Array und ein int-Array aufnimmt und ein 3D-Array zurückgibt.

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
    }
  }
}
benj2240
quelle
0

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

Probieren Sie es online!

Chas Brown
quelle
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]spart fünf.
Jonathan Allan