Déterminant récursif 2x2

17

Le déterminant d'une matrice 2 par 2

a b
c d

est donné par ad - bc.

Étant donné une matrice de chiffres de dimensions 2 n par 2 n , n ≥ 1, sortez le résultat obtenu en calculant récursivement le déterminant de chaque sous-bloc 2 par 2 jusqu'à ce que nous atteignions un nombre unique.

Par exemple, étant donné l'entrée

3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3

Après une étape, on obtient:

(3*9 - 1*5)    (4*6 - 1*2)    =    22  22
(5*7 - 3*9)    (5*3 - 8*9)         8  -57

Et en répétant, nous obtenons:

(22*-57 - 22*8) = -1430

Par conséquent, la sortie devrait être -1430.

Règles

  • Les éléments de la matrice seront toujours des entiers à un chiffre, c'est-à-dire de 0 à 9.
  • Vous pouvez prendre des entrées dans n'importe quel format de liste ou de chaîne pratique, tant qu'aucun prétraitement des données n'est effectué. Puisque la matrice est toujours carrée, vous pouvez prendre l'entrée comme une seule liste 1D au lieu d'une liste 2D si vous le souhaitez.
  • L'entrée peut se faire via l'entrée de fonction, STDIN, l'argument de ligne de commande ou l'alternative la plus proche.
  • La sortie doit être un entier unique pour fonctionner en sortie, STDOUT ou l'alternative la plus proche. Vous ne pouvez pas sortir le seul entier dans une liste ou une matrice.
  • Vous pouvez utiliser des méthodes intégrées de manipulation des déterminants et de la matrice si votre langue les prend en charge.
  • Votre algorithme doit fonctionner en théorie pour toute entrée valide.
  • Les règles de standard s'appliquent.

Cas de test

Les cas de test suivants sont donnés sous forme de listes de style Python:

[[1,0],[0,1]] -> 1
[[1,9],[8,4]] -> -68
[[0,1,2,3],[4,5,6,7],[8,9,0,1],[2,3,4,5]] -> 40
[[3,1,4,1],[5,9,2,6],[5,3,5,8],[9,7,9,3]] -> -1430
[[9,0,0,9],[0,9,9,0],[9,0,9,0],[0,9,0,9]] -> 13122
[[1,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0],[3,2,1,0,0,0,0,0],[4,3,2,1,0,0,0,0],[5,4,3,2,1,0,0,0],[6,5,4,3,2,1,0,0],[7,6,5,4,3,2,1,0],[8,7,6,5,4,3,2,1]] -> 1
[[7,1,0,5,8,0,1,5],[9,9,6,6,1,2,4,8],[4,8,7,3,8,7,4,7],[4,6,1,9,7,0,1,7],[7,6,7,1,9,4,1,6],[8,0,0,8,5,5,9,9],[4,6,4,8,9,4,8,6],[9,0,8,7,6,2,1,5]] -> 2937504
[[1,2,3,4,5,6,7,8],[2,3,4,5,6,7,8,1],[3,4,5,6,7,8,1,2],[4,5,6,7,8,1,2,3],[5,6,7,8,1,2,3,4],[6,7,8,1,2,3,4,5],[7,8,1,2,3,4,5,6],[8,1,2,3,4,5,6,7]] -> -10549504
[[1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,1,0,1,1,1,1,1,1,0],[1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,0,0,1,1,1,1,1,0,1],[1,0,1,0,1,1,1,0,0,1,1,1,1,0,1,0],[0,0,1,1,1,0,1,1,1,1,1,1,1,0,0,0],[1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1],[1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1],[1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1],[0,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1],[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,0],[1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,0,1,0,0,1,0,1,0,1,1,1,1,1,0,1],[1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1]] -> -8

(Merci à @ MartinBüttner pour son aide dans ce défi)

Sp3000
la source
3
Fait amusant: j'ai effectué quelques expériences à ce sujet et il existe un nombre étonnamment élevé de matrices binaires avec un déterminant récursif non nul. Pour les tailles 2x2, 4x4, 8x8, 16x16, nous obtenons 6, 16488, 2229617029168687104, 3349795881591711813037585032680117995553655026185547430764970842694019448832 matrices avec déterminant différent de zéro, ce qui correspond à 37,5%, 258,887
Martin Ender
@ MartinBüttner: J'obtiens 6, 22560, 10160459763342013440, ... ce qui correspond à A055165 .
Charles
@Charles bizarre, je vais vérifier mon code
Martin Ender
@ MartinBüttner: Peut-être que nous calculons simplement deux choses différentes?
Charles
@Charles Considérons la matrice [1,0,1,0;1,1,1,1;1,1,1,1;0,0,0,1]. Le déterminant complet est zéro car il a deux lignes identiques. Celui-ci est donc une matrice singulière (c'est-à-dire non inversible) 4 × 4, il n'est donc pas compté par A055165. Cependant, le déterminant "récursif" discuté ici l'est 1*1-1*0==1. Dans la direction opposée, la matrice [0,0,0,1;1,0,0,0;0,1,0,0;0,0,1,0]a un déterminant "récursif" 0*0-0*0==0. Cependant, son déterminant complet doit être différent de zéro car ses lignes ne sont que les lignes de la matrice d'identité dans un autre ordre; et il est compté par A055165.
Jeppe Stig Nielsen

Réponses:

8

J, 21 25 octets

0{0{(_2(_2-/ .*\|:)\])^:_

Usage:

   ]input=.(3,1,4,1),(5,9,2,6),(5,3,5,8),:(9,7,9,3)
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
   (0{0{(_2(_2-/ .*\|:)\])^:_) input
_1430

À chaque étape, nous découpons la matrice en 2 par 2 et calculons chacun des déterminants résultant en la matrice d'entrée de l'étape suivante. Nous répétons ce processus jusqu'à ce que le résultat ne change pas (l'élément final est le déterminant lui-même). Nous convertissons le résultat final en un scalaire avec 0{0{.

Essayez-le en ligne ici.

randomra
la source
J'ai essayé d'utiliser la fonction de mosaïque de Cut pour ce faire, mais je n'ai pas pu jouer au golf jusqu'à votre version. 29 octets: (2 2$2)&(-/ .*;._3^:(2^.#@])) essayez-le en ligne!
Jonah
4

Mathematica, 52 40 octets

Merci à Martin Büttner pour avoir économisé 12 octets.

Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]&

Explication

BlockMap[f,expr,n]divisé expren sous-listes de taille net carte fsur chaque sous-liste. BlockMap[Det,#,{2,2}]&divisez le tableau d'entrée en blocs 2 * 2 et calculez leurs déterminants.


Cas de test

%[{{3,1,4,1},{5,9,2,6},{5,3,5,8},{9,7,9,3}}]
(* -1430 *)
njpipeorgan
la source
1
J'ai écrit une implémentation de référence dans Mathematica tout en discutant de l'idée de défi avec Sp3000 et c'est 40 octets. Il est assez similaire au vôtre, alors je vais vous donner un peu de temps pour le trouver vous-même si vous le souhaitez. :)
Martin Ender
@ MartinBüttner J'ai échoué. :(
njpipeorgan
1
Vous pouvez éviter le [[1,1]]avec Tret le Nestavec //.:Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]&
Martin Ender
@ MartinBüttner En fait, j'ai trouvé //. idée lors de la lecture de la réponse en J, mais coincé dans la recherche d'un bon moyen de faire correspondre le tableau. : P
njpipeorgan
n'hésitez pas à utiliser ma solution pour mettre à jour votre réponse
Martin Ender
3

Gelée, 20 17 octets

s€2s2U×¥/€ḅ-µL¡SS

Essayez-le en ligne! ou vérifiez tous les cas de test à la fois .

Comment ça fonctionne

s€2s2U×¥/€ḅ-µL¡SS  Main link. Input: M (matrix)

s€2                Split each row of M into pairs.
   s2              Split the result into pairs of rows.
        /€         Reduce each pair...
       ¥             by applying the following, dyadic chain:
     U                 Reverse each pair of the left argument (1st row).
      ×                Multiply element-wise with the right argument (2nd row).
          ḅ-       Convert each resulting pair from base -1 to integer.
                   This maps [a, b] -> b - a.
            µ      Turn the previous links into a monadic chain. Begin a new one.
             L     Yield the length of the input.
              ¡    Execute the previous chain L times.
                   log2(L) times would do, but who's counting?
               SS  Sum twice to turn the resulting 1x1 matrix into a scalar.
Dennis
la source
2

Haskell , 93 86 octets

EDIT: Merci à @Laikoni pour avoir raccourci ces 7 octets!

f[[a,b],[c,d]]=a*d-b*c
f m|let l=[take,drop]<*>[div(length m)2]=f[f.($b<$>m)<$>l|b<-l]

Je ne savais pas que vous pouviez mettre une instruction let avant le = et je ne me suis jamais habitué à ces opérateurs de monade. Merci encore @Laikoni

Ancienne version:

f[[a,b],[c,d]]=a*d-b*c
f m=f[[f$a$map b m|a<-l]|b<-l]where h=length m`div`2;l=[take h,drop h]

Essayez-le en ligne!

Il s'agit d'une fonction qui se reproduit de deux manières différentes. Tout d'abord, la correspondance des motifs capture le cas de base: une matrice 2x2 et fait le calcul. Je l'utilise pour faire le calcul dans le cas récursif en appelant la fonction avec une matrice 2x2 que je génère qui contient les solutions récursives. Cette matrice est générée en itérant deux fois sur un tableau de fonctions qui coupent chacune une liste en deux. Je l'applique aux lignes avec un simple appel et l'applique aux colonnes en utilisant map.

user1472751
la source
Au lieu de where h=length m`div`2;l=[take h,drop h], vous pouvez utiliser f m|let l=[take,drop]<*>[length m`div`2]=. map b mpeut être b<$>m, et [f$a$b<$>m|a<-l]peut être encore raccourci f.($b<$>m)<$>l. Au total 86 octets: [ tio.run/… Essayez-le en ligne!]
Laikoni
1

Python, 166 octets

def f(m):l=len(m)/2;g=lambda x,y:[(s[:l],s[l:])[x]for s in(m[:l],m[l:])[y]];return f(g(0,0))*f(g(1,1))-f(g(0,1))*f(g(1,0)) if l>1 else m[0][0]*m[1][1]-m[1][0]*m[0][1]

Cela passe tous les cas de test fournis. m doit être un tableau 2D (comme dans les cas de test), g sélectionne la sous-matrice.

basile-henry
la source
1

Pyth, 26

M-F*VG_HhhumgMCcR2dcG2llQQ

Suite de tests

Cela comporte deux parties: M-F*VG_Hredéfinit la fonction gpour calculer le déterminant d'une matrice deux par deux. Cela économise des octets même si nous ne l'utilisons qu'une seule fois car il décompresse les deux lignes.

L'autre partie est une grande instruction de réduction que nous appelons log_2( len( input() ) )temps. Malheureusement, effectuer une étape de réduction sur une matrice 1 par 1 entraîne le résultat dans une liste, donc nous n'obtenons pas de point fixe. La réduction consiste principalement à diviser la matrice pour obtenir des matrices 2 par 2, puis à appliquer g.

FryAmTheEggman
la source
1

MATL , 26 30 octets

`tnX^teHHhZC2Ih2#Y)pwp-tnq

L'entrée est un tableau 2D avec des lignes séparées par ;, c'est-à-dire

[3 1 4 1; 5 9 2 6; 5 3 5 8; 9 7 9 3]

Essayez-le en ligne!

`             % do...while loop
  tnX^te      %   reshape into square matrix. Implicitly asks for input the first time
  HHhZC       %   transform each 2x2 block into a column
  2Ih2#Y)     %   push matrix with rows 2,3, and also matrix with remaining rows (1,4)
  pwp-        %   multiplications and subtraction to compute the 2x2 determinants
  tnq         %   condition of do...while loop: is number of elements greater than 1?
              % implicitly end loop
              % implicitly display
Luis Mendo
la source
1

Perl 5 , 120 + 1 ( -a) = 121 octets

while($#F){@r=();for$i(@o=0..($l=sqrt@F)/2-1){push@r,$F[$k=$i*$l*2+2*$_]*$F[$k+$l+1]-$F[$k+$l]*$F[$k+1]for@o}@F=@r}say@F

Essayez-le en ligne!

Prend l'entrée comme une liste de nombres séparés par des espaces.

Xcali
la source
0

ES6, 91 octets

(a,x=0,y=0,w=a.length)=>(w>>=1)?f(a,x,y,w)*f(a,x+w,y+w,w)-f(a,x,y+w,w)*f(a,x+w,y,w):a[x][y]

Solution récursive simple.

Neil
la source
0

R , 111 octets

f=function(m)"if"((n=nrow(m))-2,f(matrix(c(f(m[x<-1:(n/2),x]),f(m[y<-x+n/2,x]),f(m[x,y]),f(m[y,y])),2)),det(m))

Essayez-le en ligne!

Prend l'entrée comme une matrice R (qui est convertie par la fonction dans l'en-tête).

Giuseppe
la source
0

Groovy, 221 189 octets (à ce stade, aurait pu utiliser Java)

f={x->b=x.size();c=b/2-1;a=(0..c).collect{i->(0..c).collect{j->z=x.toList().subList(i*2,i*2+2).collect{it.toList().subList(j*2,j*2+2)};z[0][0]*z[1][1]-z[0][1]*z[1][0];}};a.size()==1?a:f(a)}

Ancienne version merdique, qui pourrait aussi bien être Java (221 octets):

f={x->b=x.size();a=new int[b/2][b/2];for(i=0;i<b-1;i+=2){for(j=0;j<b-1;j+=2){z=x.toList().subList(i,i+2).collect{it.toList().subList(j,j+2)};a[(int)(i/2)][(int)(j/2)]=z[0][0]*z[1][1]-z[0][1]*z[1][0];}};a.size()==1?a:f(a)}

Code non golfé:

f=
{x->
  b=x.size();
  int[][]a=new int[b/2][b/2];
  for(i=0;i<b-1;i+=2) {
    for(j=0;j<b-1;j+=2) {
      z=x.toList().subList(i,i+2).collect{
        it.toList().subList(j,j+2)
      };
      a[(int)(i/2)][(int)(j/2)]=z[0][0]*z[1][1]-z[0][1]*z[1][0];
    }
  }
  a.size()==1
    ?
      a:f(a)
}
Urne de poulpe magique
la source