Rekursive 2x2-Determinante

17

Die Determinante einer 2 mal 2 Matrix

a b
c d

ist gegeben durch ad - bc.

Ausgehend von einer Ziffernmatrix mit den Dimensionen 2 n mal 2 n , n ≥ 1 wird das Ergebnis ausgegeben, das durch rekursives Berechnen der Determinante jedes 2 mal 2-Unterblocks erhalten wird, bis eine einzelne Zahl erreicht ist.

Zum Beispiel angesichts der Eingabe

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

Nach einem Schritt erhalten wir:

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

Und wenn wir noch einmal iterieren, erhalten wir:

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

Daher sollte die Ausgabe sein -1430.

Regeln

  • Die Elemente der Matrix sind immer einstellige Ganzzahlen, dh 0 bis 9.
  • Sie können Eingaben in einem beliebigen Listen- oder Zeichenfolgeformat vornehmen, sofern keine Datenvorverarbeitung erfolgt. Da die Matrix immer quadratisch ist, können Sie Eingaben als einzelne 1D-Liste anstelle einer 2D-Liste vornehmen, wenn Sie dies wünschen.
  • Die Eingabe kann über Funktionseingabe, STDIN, Befehlszeilenargument oder die nächstgelegene Alternative erfolgen.
  • Die Ausgabe sollte eine einzelne Ganzzahl für die Funktionsausgabe, STDOUT oder die nächstgelegene Alternative sein. Sie können die einzelne Ganzzahl in einer Liste oder Matrix nicht ausgeben.
  • Sie können eingebaute Determinanten- und Matrixmanipulationsmethoden verwenden, wenn Ihre Sprache diese unterstützt.
  • Ihr Algorithmus muss theoretisch für jede gültige Eingabe funktionieren.
  • Es gelten die Standardregeln für .

Testfälle

Die folgenden Testfälle werden als Listen im Python-Stil angegeben:

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

(Danke an @ MartinBüttner für die Hilfe bei dieser Herausforderung)

Sp3000
quelle
3
Eine lustige Tatsache: Ich habe einige Experimente dazu durchgeführt und es gibt eine überraschend große Anzahl von binären Matrizen mit einer rekursiven Determinante ungleich Null. Für die Größen 2 x 2, 4 x 4, 8 x 8, 16 x 16 erhalten wir 6, 16488, 2229617029168687104, 3349795881591711813037585032680117995553655026185547430764970842694019448832.
Martin Ender
@ MartinBüttner: Ich bekomme 6, 22560, 10160459763342013440, ... was A055165 entspricht .
Charles
@ Charles ungerade, ich werde meinen Code überprüfen
Martin Ender
@ MartinBüttner: Möglicherweise rechnen wir nur zwei verschiedene Dinge?
Charles
@ Charles Betrachten Sie die Matrix [1,0,1,0;1,1,1,1;1,1,1,1;0,0,0,1]. Die vollständige Determinante davon ist Null, da es zwei identische Zeilen hat. Diese ist daher eine singuläre (dh nicht invertierbare) 4 × 4-Matrix und wird daher von A055165 nicht gezählt. Die hier diskutierte "rekursive" Determinante ist jedoch 1*1-1*0==1. In der entgegengesetzten Richtung hat die Matrix [0,0,0,1;1,0,0,0;0,1,0,0;0,0,1,0]eine "rekursive" Determinante 0*0-0*0==0. Seine vollständige Determinante darf jedoch nicht Null sein, da seine Zeilen nur die Zeilen der Identitätsmatrix in einer anderen Reihenfolge sind. und es wird von A055165 gezählt.
Jeppe Stig Nielsen

Antworten:

8

J, 21-25 Bytes

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

Verwendung:

   ]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

Bei jedem Schritt schneiden wir die Matrix in 2-mal-2-Werte auf und berechnen jeweils die Determinante, die zur Eingangsmatrix des nächsten Schritts führt. Wir wiederholen diesen Vorgang, bis sich das Ergebnis nicht mehr ändert (das letzte Element ist die Determinante selbst). Wir konvertieren das Endergebnis in einen Skalar mit 0{0{.

Probieren Sie es hier online aus.

randomra
quelle
Es wurde versucht, die Kachelfunktion von Cut zu verwenden, aber es konnte nicht so weit wie in Ihrer Version gespielt werden. 29 Bytes: (2 2$2)&(-/ .*;._3^:(2^.#@])) Probieren Sie es online!
Jonah
4

Mathematica, 52 40 Bytes

Vielen Dank an Martin Büttner für die Einsparung von 12 Bytes.

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

Erläuterung

BlockMap[f,expr,n]Aufteilung exprin Unterlisten der Größe nund Zuordnung fauf jeder Unterliste. BlockMap[Det,#,{2,2}]&Teilen Sie das Eingabearray in 2 * 2 Blöcke auf und berechnen Sie deren Determinanten.


Testfall

%[{{3,1,4,1},{5,9,2,6},{5,3,5,8},{9,7,9,3}}]
(* -1430 *)
njpipeorgan
quelle
1
Ich habe eine Referenzimplementierung in Mathematica geschrieben, während ich die Challenge-Idee mit Sp3000 und ihren 40 Bytes besprochen habe. Es ist ziemlich ähnlich wie deins, also gebe ich dir etwas Zeit, es selbst zu finden, wenn du magst. :)
Martin Ender
@ MartinBüttner Ich habe versagt. :(
njpipeorgan
1
Sie können das [[1,1]]mit Trund das Nestmit vermeiden //.:Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]&
Martin Ender
@ MartinBüttner Eigentlich habe ich mir // ausgedacht. Idee beim Lesen der Antwort in J, aber stecken in der Suche nach einem guten Weg, um das Array abzustimmen. : P
njpipeorgan
Fühlen Sie sich frei, meine Lösung zu verwenden, um Ihre Antwort zu aktualisieren
Martin Ender
3

Jelly, 20 17 Bytes

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

Probieren Sie es online! oder überprüfen Sie alle Testfälle auf einmal .

Wie es funktioniert

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

Haskell , 93 86 Bytes

EDIT: Danke an @Laikoni für die Verkürzung um ganze 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]

Ich wusste nicht, dass Sie eine let-Anweisung vor das = setzen können, und ich habe mich nie an diese Monadenoperatoren gewöhnt. Nochmals vielen Dank @Laikoni

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

Probieren Sie es online!

Dies ist eine Funktion, die sich auf zwei verschiedene Arten wiederholt. Zuerst fängt der Mustervergleich den Basisfall ein: eine 2x2-Matrix und es wird die Berechnung durchgeführt. Ich benutze dies, um die Berechnung im rekursiven Fall durchzuführen, indem ich die Funktion mit einer von mir generierten 2x2-Matrix aufrufe, die die rekursiven Lösungen enthält. Diese Matrix wird durch zweimaliges Durchlaufen einer Reihe von Funktionen erzeugt, die jeweils eine Liste in zwei Hälften zerlegen. Ich wende es mit einem einfachen Aufruf auf Zeilen an und wende es mit auf Spalten an map.

user1472751
quelle
Stattdessen where h=length m`div`2;l=[take h,drop h]können Sie verwenden f m|let l=[take,drop]<*>[length m`div`2]=. map b mkann sein b<$>m, und [f$a$b<$>m|a<-l]kann weiter verkürzt werden f.($b<$>m)<$>l. Insgesamt 86 Bytes: [ tio.run/… Online
testen
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]

Damit sind alle bereitgestellten Testfälle bestanden. m muss ein 2D-Array sein (wie in den Testfällen), g wählt die Submatrix aus.

Basilikum-Henry
quelle
1

Pyth, 26

M-F*VG_HhhumgMCcR2dcG2llQQ

Test Suite

Dies hat zwei Teile: M-F*VG_HDefiniert die Funktion gzur Berechnung der Determinante einer Zwei-mal-Zwei-Matrix neu. Das spart Bytes, obwohl wir es nur einmal verwenden, weil es die beiden Zeilen entpackt.

Der andere Teil ist eine große Reduce-Anweisung, die wir log_2( len( input() ) )Zeiten nennen . Unglücklicherweise wird das Ergebnis in eine Liste eingeschlossen, wenn ein Schritt in der Verkleinerung einer 1-zu-1-Matrix ausgeführt wird, sodass wir keinen festen Punkt erhalten. Das Reduzieren ist meistens nur das Aufteilen der Matrix, um 2 mal 2 Matrizen zu erhalten und dann anzuwenden g.

FryAmTheEggman
quelle
1

MATL , 26 30 Bytes

`tnX^teHHhZC2Ih2#Y)pwp-tnq

Eingabe ist eine 2D - Array mit Reihen , getrennt durch ;, das heißt,

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

Probieren Sie es online!

`             % 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
quelle
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

Probieren Sie es online!

Nimmt die Eingabe als Liste mit durch Leerzeichen getrennten Zahlen.

Xcali
quelle
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]

Einfache rekursive Lösung.

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

Probieren Sie es online!

Übernimmt die Eingabe als R-Matrix (die von der Funktion im Header konvertiert wird).

Giuseppe
quelle
0

Groovy, 221 189 Bytes (Zu diesem Zeitpunkt hätte Java verwendet werden können)

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

Alte beschissene Version, die genauso gut Java sein könnte (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)}

Ungolfed-Code:

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)
}
Magische Kraken-Urne
quelle