Determinante recursivo 2x2

17

El determinante de una matriz 2 por 2

a b
c d

está dada por ad - bc.

Dada una matriz de dígitos con dimensiones 2 n por 2 n , n ≥ 1, genera el resultado obtenido calculando recursivamente el determinante de cada subbloque 2 por 2 hasta llegar a un solo número.

Por ejemplo, dada la entrada

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

Después de un paso, obtenemos:

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

E iterando una vez más, obtenemos:

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

Por lo tanto, la salida debería ser -1430.

Reglas

  • Los elementos de la matriz siempre serán enteros de un solo dígito, es decir, de 0 a 9.
  • Puede tomar la entrada en cualquier lista conveniente o formato de cadena, siempre que no se realice un procesamiento previo de los datos. Dado que la matriz siempre es cuadrada, puede tomar la entrada como una sola lista 1D en lugar de una lista 2D si lo desea.
  • La entrada puede ser a través de la entrada de función, STDIN, argumento de línea de comando o la alternativa más cercana.
  • La salida debe ser un solo entero para funcionar con salida, STDOUT o la alternativa más cercana. No puede generar el entero único en una lista o matriz.
  • Puede utilizar métodos de manipulación de determinantes y matrices incorporados si su idioma los respalda.
  • Su algoritmo debe funcionar en teoría para cualquier entrada válida.
  • Aplican reglas estándar de código de golf .

Casos de prueba

Los siguientes casos de prueba se dan como listas de estilo 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

(Gracias a @ MartinBüttner por la ayuda con este desafío)

code-golf arithmetic linear-algebra matrix Sp3000
fuente
3
Dato curioso: realicé algunos experimentos sobre esto y hay una cantidad sorprendentemente grande de matrices binarias con determinante recursivo distinto de cero. Para los tamaños 2x2, 4x4, 8x8, 16x16, obtenemos 6, 16488, 2229617029168687104, 3349795881591711813037585032680117995553655026185547430764970842694019448832 matrices con determinante no nulo, que corresponde a 37.5%, 28%, 28%, que corresponde a 37.5% .28%, 28%, 28%, 28%, 28%, 28%, 28%, 28%, 28%, 28%, 28%, 28%, 28%, 28%, 28%, 28%, 28%, 28%, 28%, 286%, 28%, 748%, 284%, 284%, 28%, 29%, 28%.
Martin Ender
@ MartinBüttner: obtengo 6, 22560, 10160459763342013440, ... que coincide con A055165 .
Charles
@Charles extraño, revisaré mi código
Martin Ender
@ MartinBüttner: ¿Posiblemente solo estamos calculando dos cosas diferentes?
Charles
@ Charles Considere la matriz [1,0,1,0;1,1,1,1;1,1,1,1;0,0,0,1]. El determinante completo es cero, ya que tiene dos filas idénticas. Por lo tanto, esta es una matriz 4 × 4 singular (es decir, no invertible), por lo que A055165 no la cuenta. Sin embargo, el determinante "recursivo" discutido aquí es 1*1-1*0==1. En la dirección opuesta, la matriz [0,0,0,1;1,0,0,0;0,1,0,0;0,0,1,0]tiene determinante "recursivo" 0*0-0*0==0. Sin embargo, su determinante completo debe ser distinto de cero porque sus filas son solo las filas de la matriz de identidad en otro orden; y se cuenta por A055165.
Jeppe Stig Nielsen

Respuestas:

8

J, 21 25 bytes

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

Uso:

   ]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

En cada paso, cortamos la matriz a 2 por 2 y calculamos cada uno determinante que resulta en la matriz de entrada del siguiente paso. Repetimos este proceso hasta que el resultado no cambie (el elemento final es el determinante mismo). Convertimos el resultado final a un escalar con 0{0{.

Pruébelo en línea aquí.

randomra
fuente
Intenté usar la función de mosaico de Cut para hacer esto, pero no pude jugar golf en tu versión. 29 bytes: ¡ (2 2$2)&(-/ .*;._3^:(2^.#@])) Pruébelo en línea!
Jonás
4

Mathematica, 52 40 bytes

Gracias a Martin Büttner por guardar 12 bytes.

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

Explicación

BlockMap[f,expr,n]dividir expren sublistas de tamaño ny mapa fen cada sublista. BlockMap[Det,#,{2,2}]&divide la matriz de entrada en bloques 2 * 2 y calcula sus determinantes.

Caso de prueba

%[{{3,1,4,1},{5,9,2,6},{5,3,5,8},{9,7,9,3}}]
(* -1430 *)
njpipeorgan
fuente
1
Escribí una implementación de referencia en Mathematica mientras discutía la idea del desafío con Sp3000 y son 40 bytes. Sin embargo, es bastante similar al tuyo, así que te daré algo de tiempo para encontrarlo tú mismo si lo deseas. :)
Martin Ender
@ MartinBüttner fallé. :(
njpipeorgan
1
Puede evitar el [[1,1]]con Try el Nestcon //.:Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]&
Martin Ender
@ MartinBüttner En realidad, se me ocurrió //. idea al leer la respuesta en J, pero atascado en encontrar una buena manera de hacer coincidir la matriz. : P
njpipeorgan
siéntase libre de usar mi solución para actualizar su respuesta
Martin Ender
3

Jalea, 20 17 bytes

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

Pruébalo en línea! o verificar todos los casos de prueba a la vez .

Cómo funciona

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
fuente
2

Haskell , 93 86 bytes

EDITAR: ¡Gracias a @Laikoni por acortar esto un total de 7 bytes!

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]

No sabía que podía poner una declaración let antes de = y nunca me he acostumbrado a esos operadores de mónada. Gracias de nuevo @Laikoni

Versión antigua:

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]

Pruébalo en línea!

Esta es una función que se repite en sí misma de dos maneras diferentes. Primero, la coincidencia de patrones captura el caso base: una matriz de 2x2 y realiza el cálculo. Utilizo esto para hacer el cálculo en el caso recursivo llamando a la función con una matriz 2x2 que genero que tiene las soluciones recursivas. Esa matriz se genera iterando dos veces sobre una matriz de funciones que cada una corta una lista a la mitad. Lo aplico a filas con una simple llamada y lo aplico a columnas usando map.

usuario1472751
fuente
En lugar de where h=length m`div`2;l=[take h,drop h], puedes usar f m|let l=[take,drop]<*>[length m`div`2]=. map b mpuede ser b<$>m, y [f$a$b<$>m|a<-l]puede acortarse aún más f.($b<$>m)<$>l. En total 86 bytes: [ tio.run/… ¡ Pruébelo en línea!]
Laikoni
1

Python, 166 bytes

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]

Esto pasa todos los casos de prueba proporcionados. m tiene que ser una matriz 2D (como en los casos de prueba), g selecciona la submatriz.

basile-henry
fuente
1

Pyth, 26

M-F*VG_HhhumgMCcR2dcG2llQQ

Banco de pruebas

Esto tiene dos partes: M-F*VG_H redefine la función gpara calcular el determinante de una matriz de dos por dos. Esto ahorra bytes aunque solo lo usemos una vez porque desempaqueta las dos filas.

La otra parte es una gran declaración de reducción que llamamos log_2( len( input() ) )tiempos. Desafortunadamente, realizar un paso en la reducción en una matriz 1 por 1 hace que el resultado quede envuelto en una lista, por lo que no obtenemos un punto fijo. La reducción consiste principalmente en dividir la matriz para obtener 2 por 2 matrices y luego aplicar g.

FryAmTheEggman
fuente
1

MATL , 26 30 bytes

`tnX^teHHhZC2Ih2#Y)pwp-tnq

La entrada es una matriz 2D con filas separadas por ;, es decir,

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

Pruébalo en línea!

`             % 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
fuente
1

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

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

Pruébalo en línea!

Toma la entrada como una lista de números separados por espacios.

Xcali
fuente
0

ES6, 91 bytes

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

Solución recursiva directa.

Neil
fuente
0

R , 111 bytes

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

Pruébalo en línea!

Toma la entrada como una matriz R (que es convertida por la función en el encabezado).

Giuseppe
fuente
0

Groovy, 221 189 bytes (en este punto, podría haber usado 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)}

Antigua versión de mierda, que también podría ser Java (221 bytes):

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

Código sin 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)
}
Urna de pulpo mágico
fuente