Penentu 2x2 rekursif

17

Penentu 2 2 matriks

a b
c d

diberikan oleh ad - bc.

Diberikan matriks digit dengan dimensi 2 n oleh 2 n , n ≥ 1, output hasil yang diperoleh dengan menghitung secara rekursif penentu masing-masing 2 oleh 2 sub-blok sampai kita mencapai angka tunggal.

Misalnya diberi input

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

Setelah satu langkah, kami memperoleh:

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

Dan iterasi sekali lagi, kita dapatkan:

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

Oleh karena itu, hasilnya harus -1430.

Aturan

  • Elemen-elemen dari matriks akan selalu berupa bilangan bulat satu digit, yaitu 0 hingga 9.
  • Anda dapat mengambil input dalam format string atau daftar yang mudah, selama tidak ada pemrosesan data yang dilakukan. Karena matriks selalu persegi, Anda dapat mengambil input sebagai daftar 1D tunggal, bukan daftar 2D jika Anda mau.
  • Input dapat melalui input fungsi, STDIN, argumen baris perintah atau alternatif terdekat.
  • Output harus berupa bilangan bulat tunggal untuk berfungsi output, STDOUT atau alternatif terdekat. Anda tidak dapat mengeluarkan bilangan bulat tunggal dalam daftar atau matriks.
  • Anda dapat menggunakan metode determinan dan manipulasi matriks bawaan jika bahasa Anda mendukungnya.
  • Algoritme Anda harus bekerja secara teori untuk input yang valid.
  • Aturan standar berlaku.

Uji kasus

Kasing uji berikut diberikan sebagai daftar gaya-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

(Terima kasih kepada @ MartinBüttner untuk bantuan dengan tantangan ini)

Sp3000
sumber
3
Fakta menyenangkan: Saya menjalankan beberapa eksperimen tentang ini dan ada sejumlah besar matriks biner dengan determinan rekursif non-nol. Untuk ukuran 2x2, 4x4, 8x8, 16x16, kami mendapatkan 6, 16488, 2229617029168687104, 3349795881591711813037585032680117995553655026185547430764970842694019448832 masing-masing dengan%%, masing-masing%%,%, dengan%%, masing-masing%%,%.
Martin Ender
@ MartinBüttner: Saya mendapatkan 6, 22560, 10160459763342013440, ... yang cocok dengan A055165 .
Charles
@ Charles aneh, saya akan memeriksa kode saya
Martin Ender
@ MartinBüttner: Mungkin kita hanya menghitung dua hal yang berbeda?
Charles
@ Charles Pertimbangkan matriks [1,0,1,0;1,1,1,1;1,1,1,1;0,0,0,1]. Penentu penuhnya adalah nol karena memiliki dua baris yang identik. Oleh karena itu, ini adalah matriks 4 × 4 singular (artinya tidak dapat dibalik), sehingga tidak dihitung oleh A055165. Namun, penentu "rekursif" yang dibahas di sini adalah 1*1-1*0==1. Dalam arah yang berlawanan, matriks [0,0,0,1;1,0,0,0;0,1,0,0;0,0,1,0]memiliki penentu "rekursif" 0*0-0*0==0. Namun, penentu penuhnya harus non-nol karena barisnya hanya baris dari matriks identitas dalam urutan lain; dan itu dihitung oleh A055165.
Jeppe Stig Nielsen

Jawaban:

8

J, 21 25 byte

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

Pemakaian:

   ]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

Pada setiap langkah kami memotong matriks menjadi 2-oleh-2 dan menghitung setiap penentu yang menghasilkan matriks input langkah selanjutnya. Kami ulangi proses ini sampai hasilnya tidak berubah (elemen terakhir adalah penentu itu sendiri). Kami mengonversi hasil akhir menjadi skalar dengan 0{0{.

Cobalah online di sini.

randomra
sumber
Sudah mencoba menggunakan fungsi ubin Cut untuk melakukan ini, tetapi tidak dapat golf sejauh versi Anda. 29 byte: (2 2$2)&(-/ .*;._3^:(2^.#@])) Cobalah online!
Jonah
4

Mathematica, 52 40 byte

Terima kasih kepada Martin Büttner karena telah menghemat 12 byte.

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

Penjelasan

BlockMap[f,expr,n]dibagi exprmenjadi sublists ukuran ndan petaf di setiap sublists. BlockMap[Det,#,{2,2}]&pisahkan array input menjadi 2 * 2 blok dan hitung determinannya.


Kasus cobaan

%[{{3,1,4,1},{5,9,2,6},{5,3,5,8},{9,7,9,3}}]
(* -1430 *)
njpipeorgan
sumber
1
Saya menulis implementasi referensi dalam Mathematica sambil mendiskusikan ide tantangan dengan Sp3000 dan 40 byte. Ini sangat mirip dengan milikmu, jadi aku akan memberimu waktu untuk menemukannya sendiri jika kamu mau. :)
Martin Ender
@ MartinBüttner saya gagal. :(
njpipeorgan
1
Anda dapat menghindari [[1,1]]dengan Trdan Nestdengan //.:Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]&
Martin Ender
@ MartinBüttner Sebenarnya, saya datang dengan //. Ide ketika membaca jawaban dalam J, tetapi terjebak dalam menemukan cara yang baik untuk mencocokkan array. : P
njpipeorgan
jangan ragu untuk menggunakan solusi saya untuk memperbarui jawaban Anda
Martin Ender
3

Jelly, 20 17 byte

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

Cobalah online! atau verifikasi semua kasus uji sekaligus .

Bagaimana itu bekerja

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

Haskell , 93 86 byte

SUNTING: Terima kasih kepada @Laikoni untuk mempersingkat keseluruhan 7 byte ini!

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]

Saya tidak tahu Anda bisa memberikan pernyataan let sebelum = dan saya tidak pernah terbiasa dengan operator monad itu. Terima kasih lagi @Laikoni

Versi lama:

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]

Cobalah online!

Ini adalah fungsi yang berulang pada dirinya sendiri dalam dua cara berbeda. Pertama pencocokan pola menangkap kasus dasar: matriks 2x2 dan melakukan perhitungan. Saya menggunakan ini untuk melakukan perhitungan dalam kasus rekursif dengan memanggil fungsi dengan matriks 2x2 yang saya hasilkan yang memiliki solusi rekursif di dalamnya. Matriks itu dihasilkan dengan mengulangi dua kali lebih dari satu array fungsi yang masing-masing memotong daftar menjadi dua. Saya menerapkannya pada baris dengan panggilan sederhana dan menerapkannya ke kolom menggunakan map.

pengguna1472751
sumber
Alih-alih where h=length m`div`2;l=[take h,drop h], Anda bisa menggunakan f m|let l=[take,drop]<*>[length m`div`2]=. map b mdapat b<$>m, dan [f$a$b<$>m|a<-l]dapat disingkat menjadi f.($b<$>m)<$>l. Secara keseluruhan 86 byte: [ tio.run/... Cobalah online!]
Laikoni
1

Python, 166 byte

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]

Ini melewati semua kasus uji yang disediakan. m harus berupa array 2D (seperti dalam kasus uji), g memilih sub matriks.

basile-henry
sumber
1

Pyth, 26

M-F*VG_HhhumgMCcR2dcG2llQQ

Test Suite

Ini memiliki dua bagian: M-F*VG_Hmendefinisikan kembali fungsig untuk menghitung determinan matriks dua demi dua. Ini menghemat byte meskipun kami hanya menggunakannya sekali karena membongkar dua baris.

Bagian lainnya adalah pernyataan pengurangan besar yang kita sebut log_2( len( input() ) )waktu. Sayangnya, melakukan langkah dalam pengurangan pada matriks 1 oleh 1 menyebabkan hasilnya dibungkus dalam daftar, jadi kami tidak mendapatkan titik tetap. Pengurangan sebagian besar hanya membagi matriks untuk mendapatkan 2 oleh 2 matriks dan kemudian menerapkan g.

FryAmTheEggman
sumber
1

MATL , 26 30 byte

`tnX^teHHhZC2Ih2#Y)pwp-tnq

Input adalah array 2D dengan baris yang dipisahkan oleh ;, yaitu,

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

Cobalah 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
sumber
1

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

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

Cobalah online!

Mengambil input sebagai daftar angka yang dipisahkan spasi.

Xcali
sumber
0

ES6, 91 byte

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

Solusi rekursif langsung.

Neil
sumber
0

R , 111 byte

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

Cobalah online!

Mengambil input sebagai matriks R (yang dikonversi oleh fungsi di header).

Giuseppe
sumber
0

Groovy, 221 189 bytes (Pada titik ini, bisa menggunakan 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)}

Versi jelek lama, yang mungkin juga Java (221 byte):

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

Kode tidak dikunci:

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)
}
Guci Gurita Ajaib
sumber