Générer toutes les sous-matrices carrées d'une taille donnée

14

Vous recevrez une matrice carrée d'entiers M et un autre entier positif n , strictement inférieur à la taille de M . Votre tâche consiste à générer toutes les sous-matrices carrées de M de taille n .

Aux fins de ce problème, une sous-matrice carrée est un groupe de voisins des rangées et des colonnes contenues dans M .

Formats d'entrée / sortie

Vous êtes libre de choisir tout autre format raisonnable, ce ne sont que quelques exemples.

Contribution

  • Une matrice dans le type de matrice native (si votre langue en a une)
  • Un tableau 2D (un tableau de tableaux 1D, chacun correspondant à une ligne / une colonne)
  • Un tableau 1D (puisque la matrice est toujours carrée)
  • Une chaîne (vous avez choisi l'espacement, mais n'en abusez pas), etc.

Production

  • Une matrice de matrices.
  • Un tableau 4D, où chaque élément (liste 3D) représente les sous-matrices sur une ligne / colonne.
  • Un tableau 3D, où chaque élément (liste 2D) représente une sous-matrice.
  • Une représentation sous forme de chaîne des sous-matrices résultantes, etc.

Spécifications

  • Vous pouvez également choisir de prendre la taille de M comme entrée. Il est garanti d'être au moins 2 .
  • L'orientation de la sortie est arbitraire: vous pouvez choisir de sortir les sous-matrices sous forme de listes de colonnes ou de listes de lignes, mais votre choix doit être cohérent.
  • Vous pouvez concurrencer dans n'importe quel langage de programmation et pouvez prendre des entrées et fournir des sorties par n'importe quelle méthode standard , tout en prenant note que ces échappatoires sont interdites par défaut.
  • Il s'agit de , donc la soumission la plus courte (en octets) pour chaque langue l' emporte.

Exemple

Étant donné n = 3 et M :

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

Les sous - matrices 3x3 possibles sont:

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

Le résultat serait donc:

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

Comme indiqué ci-dessus, une sortie 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]]]

serait également acceptable si vous choisissez de renvoyer les sous-matrices sous forme de listes de lignes.

Cas de test

Les entrées 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

Et les sorties correspondantes (sous-matrices données sous forme de listes de lignes):

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

Ou, sous forme de listes de colonnes:

[[[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]]]]
M. Xcoder
la source
Publication Sandbox (désormais supprimée, seuls les utilisateurs ayant une réputation supérieure à 2k peuvent la consulter). Merci à tous ceux qui ont donné leur avis.
M. Xcoder
Alors, ce format de sortie est- il autorisé?
Luis Mendo
@LuisMendo Oui, c'est autorisé.
M. Xcoder

Réponses:

6

05AB1E , 8 octets

2FεŒsù}ø

Essayez-le en ligne!

Explication

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
la source
5

MATL , 4 octets

thYC

Les entrées sont ndonc M.

La sortie est une matrice, où chaque colonne contient toutes les colonnes d'une sous-matrice.

Essayez-le en ligne!

Explication

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

Plus sérieusement, tprend l'entrée n implicitement et la duplique sur la pile. hconcatène les deux copies de n , produisant le tableau [n, n] . YCprend implicitement l' entrée M , extrait tous ses blocs de taille [n, n] et les organise sous forme de colonnes dans l'ordre des colonnes principales. Cela signifie que les colonnes de chaque bloc sont empilées verticalement pour former une seule colonne.

Luis Mendo
la source
1
LOL +1 pour "pronom formel, légèrement démodé", et un très beau golf.
Giuseppe
@Giuseppe Je viens de réaliser que c'est un déterminant, pas un pronom: - /
Luis Mendo
Eh bien, j'ai toujours appris "ton / ton" comme pronoms possessifs; c'est la première fois que j'entends parler d'un déterminant!
Giuseppe
@Giuseppe "Thy / your" sont des déterminants possessifs, c'est-à-dire qu'ils vont avec un nom: "This is your car". "Thine / yours" sont des pronoms possessifs, c'est-à-dire que le nom est omis: "This is yours". Et j'ai d'abord confondu "ton" avec un pronom personnel, qui serait en fait "toi". Quel gâchis j'ai fait :-)
Luis Mendo
4

APL (Dyalog Unicode) , 26 octets SBCS

Infixe anonyme lambda prenant n comme argument de gauche et M comme argument de droite.

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

Essayez-le en ligne!

{} Lambda anonyme où est l'argument de gauche et l'argument de droite:

⊢⍵ produire le bon argument ( séparé ⍺ ⍺de )

⊢⌺⍺ ⍺ tous les -by- sous - matrices , y compris celles qui se chevauchent les bords (ceux -ci sont complétées par des zéros)

()↓ Déposez les éléments numériques suivants le long des deux premières dimensions:

  ⍺÷2 moitié de

  ¯1+ négatif plus que

   rassembler

  2⍴ cyclique r Eshape à une liste de deux éléments

  s← stocker dans s(pour les disques durs)

  - nier (c.-à-d. tomber de l'arrière)

s↓déposer des séléments le long des première et deuxième dimensions (par l'avant)

Adam
la source
4

APL (Dyalog Unicode) , 31 octets

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

Essayez-le en ligne!

Une approche différente de celle d'Adam.

Erik le Outgolfer
la source
Avez-vous l'intention de fournir une explication (après avoir terminé le golf, bien sûr)? Je serais intéressé de voir comment cela fonctionne (et je ne connais pas du tout APL) :)
Emigna
@Emigna Ouais, si j'ai le temps d'ici là.
Erik the Outgolfer le
Très intelligent. Si vous pouvez utiliser dyadic avec succès pour des cas non triviaux, alors vous avez vraiment maîtrisé la programmation de tableaux.
Adám
@ Adám Uh, bien que je pense que cette réponse est en fait invalide :-( EDIT: corrigé, mais maintenant il fait 31 octets de long ...
Erik the Outgolfer
N'hésitez pas à copier la suite de tests de ma soumission.
Adám
3

R , 75 octets

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

Essayez-le en ligne!

Prend M, Net la SIze de la matrice.

Imprime les matrices résultantes sur stdout; drop=Fest nécessaire pour que dans le N=1cas où l'indexation ne supprime pas l' dimattribut et produise a matrixplutôt que a vector.

Giuseppe
la source
3

J , 11 8 octets

-3 octets grâce aux miles

<;._3~,~

Essayez-le en ligne!

Galen Ivanov
la source
1
Cela utilise 8 octets <;._3~,~et utilise un crochet à la place pour associer la taille à elle-même, puis coupe et encadre chacun car une matrice de matrices est autorisée en sortie.
miles
@miles Merci, c'est élégant maintenant!
Galen Ivanov
2

Gelée , 5 octets

Z⁹Ƥ⁺€

Utilise le format de sortie 4D. Pour la 3D, ajoutez un pour 6 octets .

Essayez-le en ligne!

Comment ça fonctionne

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
la source
J'ai suggéré quelque chose de similaire à user202729 dans le chat. Une alternative à 5 octets est ṡ€Zṡ€.
M. Xcoder
2

Brachylog , 13 octets

{tN&s₎\;Ns₎}ᶠ

Essayez-le en ligne!

Cela renvoie des listes de colonnes.

Techniquement, tN&s₎\;Ns₎c'est un prédicat générateur qui unifie sa sortie avec l'une de ces sous-matrices. Nous utilisons {…}ᶠuniquement pour exposer toutes les possibilités.

Explication

 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
Fatalize
la source
1

Stax , 10 octets

│Æ☼♂Mqß E╖

Exécuter

La représentation ascii du même programme est

YBFMyBF|PMmJ

Cela fonctionne comme ça.

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
récursif
la source
1

JavaScript (ES6), 91 octets

Prend des entrées dans la syntaxe de curry (a)(n). Renvoie les résultats sous forme de listes de lignes.

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)

Cas de test

Arnauld
la source
1

APL (Dyalog Classic) , 24 23 octets

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

Essayez-le en ligne!

le résultat est une matrice de matrices, bien que le formatage de sortie de Dyalog ne le rende pas très évident

entrez la matrice ( ), transformez chaque élément en une matrice imbriquée qui lui est propre ( ⍪¨), prenez les concaténations de préfixe par ligne ( ,\) et par colonne ( ⍪⍀), saisissez n ( ), supprimez les n-1 premières lignes et colonnes des matrices imbriquées ( (¯1-t←-2⍴⎕)↓), prenez le coin en bas à droite n par n de chaque matrice ( 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
la source
0

Rubis , 63 octets

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

Essayez-le en ligne!

Il s'agit d'un lambda prenant un tableau 2D et un int, renvoyant un tableau 3D.

Non 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
    }
  }
}
benj2240
la source
0

Python 2 , 91 octets

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

Essayez-le en ligne!

Chas Brown
la source
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]sauve cinq.
Jonathan Allan