Temukan Kekuatan Matriks

9

Masalah

Membuat program atau fungsi yang dapat menghitung hasil dari matriks diangkat ke n th kekuasaan. Kode Anda akan mengambil matriks persegi yang sewenang-wenang A dan bilangan bulat non-negatif n , dan kembali matriks dengan nilai A n .

Batasan

Fungsi bawaan yang menghitung daya matriks dan produk matriks tidak diizinkan.

Sisa aturan standar untuk kode-golf berlaku.

Penjelasan

Diberikan matriks kuadrat A , nilai A n = AA ⋯ A (produk matriks berulang dari A dengan dirinya sendiri, n kali). Jika n positif, standar yang baru saja disebutkan digunakan. Ketika n adalah nol, matriks identitas dengan urutan A yang sama adalah hasilnya.

Tujuan

Ini adalah kode-golf dan kode terpendek menang.

Uji Kasus

Di sini, A adalah matriks input, n adalah integer input, dan r adalah matriks output di mana r = A n .

n = 0
A = 62 72
    10 34
r =  1  0
     0  1

n = 1
A = 23 61 47
    81 11 60
    42  9  0
r = 23 61 47
    81 11 60
    42  9  0

n = 2
A =  12  28 -26  3
     -3 -10 -13  0
     25  41   3 -4
    -20 -14  -4 29
r = -650 -1052  -766 227
    -331  -517   169  43
     332   469 -1158 -53
    -878  -990   574 797

n = 4
A = -42 -19  18 -38
    -33  26 -13  31
    -43  25 -48  28
     34 -26  19 -48
r = -14606833  3168904 -6745178  4491946
      1559282  3713073 -4130758  7251116
      8097114  5970846 -5242241 12543582
     -5844034 -4491274  4274336 -9196467

n = 5
A =  7  0 -3  8 -5  6 -6
     6  7  1  2  6 -3  2
     7  8  0  0 -8  5  2
     3  0  1  2  4 -3  4
     2  4 -1 -7 -4 -1 -8
    -3  8 -9 -2  7 -4 -8
    -4 -5 -1  0  5  5 -1
r =  39557  24398 -75256 131769  50575   14153  -7324
    182127  19109   3586 115176 -23305    9493 -44754
    146840  31906 -23476 190418 -38946   65494  26468
     42010 -21876  41060 -13950 -55148   19290   -406
     44130  34244 -35944  34272  22917  -39987 -54864
      1111  40810 -92324  35831 215711 -117849 -75038
    -70219   8803 -61496   6116  45247   50166   2109
mil
sumber
3
Bagaimana dengan built-in untuk produk matriks atau inversi matriks?
Dennis
@ Dennis Saya sedang mempertimbangkan untuk melarang mereka juga, tapi rasanya terlalu membatasi.
mil
2
Untuk bahasa tanpa pembalikan matriks bawaan, ini mengejutkan saya sebagai tantangan bunglon karena membalikkan matriks dari awal tampaknya jauh lebih sulit daripada mengambil produk yang diulang.
xnor
2
Saya setuju dengan @xnor. Dan bagaimana jika suatu bahasa tidak memiliki inversi matriks tetapi memiliki kekuatan matriks? Apakah A^-1bisa digunakan sebagai pengganti inv(A)?
Luis Mendo
1
Apakah exp(k*log(M))diperbolehkan? (Meskipun mungkin tidak berfungsi karena cabang yang tidak unik.)
xnor

Jawaban:

4

Jelly , 17 16 15 byte

Z×'³S€€
LṬ€z0Ç¡

Cobalah online!

Permalinks dengan output grid: test case 1 | test case 2 | test case 3 | test case 4 | test case 5

Bagaimana itu bekerja

LṬ€z0Ç¡  Main link. Arguments: A (matrix), n (power)

L        Get the length l of A.
 Ṭ€      Turn each k in [1, ..., l] into a Boolean list [0, 0, ..., 1] of length k.
   z0    Zip; transpose the resulting 2D list, padding with 0 for rectangularity.
         This constructs the identity matrix of dimensions k×k.
     Ç¡  Execute the helper link n times.

Z×'³S€€  Helper link. Argument: B (matrix)

Z        Zip; transpose rows and columns of B.
   ³     Yield A.
 ×'      Spawned multiplication; element-wise mutiply each rows of zipped B (i.e.,
         each column of B) with each row of A.
         This is "backwards", but multiplication of powers of A is commutative.
    S€€  Compute the sum of each product of rows.
Dennis
sumber
5

MATL , 20 byte

XJZyXyi:"!J2$1!*s1$e

Cobalah online!

Penjelasan

Ini menghindari perkalian matriks dengan melakukannya secara manual, menggunakan perkalian elemen-bijaksana dengan siaran diikuti oleh penjumlahan vektor. Secara khusus, untuk melipatgandakan matriks Mdan N, keduanya berukuran s × s :

  1. Transpose M. Panggil matriks yang dihasilkan P.
  2. Permutasi pada dimensi Nsehingga Nadalah "berubah" dengan sumbu rotasi sepanjang dimensi pertama, memberikan s × 1 × s Array 3D, mengatakan Q.
  3. Lipat gandakan setiap elemen dari Psetiap elemen Q, dengan siaran implisit. Ini berarti bahwa Psecara otomatis direplikasi s kali sepanjang dimensi ketiga, dan Qdireplikasi s kali di sepanjang kedua, membuat mereka berdua s × s × s , sebelum perkalian elemen-bijaksana yang sebenarnya terjadi.
  4. Jumlahkan sepanjang dimensi pertama untuk menghasilkan array 1 × s × s .
  5. Peras dimensi singleton terkemuka keluar, untuk menghasilkan hasil s × s .

Kode yang dikomentari:

XJ      % take matrix A. Copy to clipboard J
ZyXy    % generate identity matrix of the same size
i:      % take exponent n. Generate range [1 2 ... n] (possibly empty)
"       % for each element in that range
  !     %   transpose matrix with product accumulated up to now (this is step 1)
  J     %   paste A
  2$1!  %   permute dimensions: rotation along first-dimension axis (step 2)
  *     %   element-wise multiplication with broadcast (step 3)
  s     %   sum along first dimension (step 4)
  1$e   %   squeeze out singleton dimension, i.e. first dimension (step 5)
        % end for. Display
Luis Mendo
sumber
Gagal 0 ....
CalculatorFeline
@CatsAreFluffy Terima kasih! Diperbaiki
Luis Mendo
3

APL, 32 31 karakter

{⍺=0:(⍴⍵)⍴1⍨1+≢⍵⋄+.×⍨⍣(⍺-1)⊣⍵}

Argumen kiri kekuatan untuk menaikkan, argumen kanan matriks. Bit yang paling sulit (paling memakan ruang) adalah membangun matriks identitas untuk kasus di mana eksponen yang diinginkan adalah 0. Perhitungan yang sebenarnya didasarkan pada kenyataan bahwa produk dalam yang digeneralisasi ( .) dengan +dan ×sebagai operan secara efektif adalah produk matriks. Ini dikombinasikan dengan operator daya ("repeat") membentuk daging dari solusi.

lstefano
sumber
1: Apakah kamu THE Stefano yang mengalahkan Dan & Nick satu byte di game tahun 2016 ?! 2. (1+≢⍵)↑1=> 1↑⍨1+≢⍵untuk menyimpan satu byte.
Zacharý
Ya itu aku.
lstefano
2

Sage, 112 byte

lambda A,n:reduce(lambda A,B:[[sum(map(mul,zip(a,b)))for b in zip(*B)]for a in A],[A]*n,identity_matrix(len(A)))

Cobalah online

Penjelasan:

Inner lambda ( lambda A,B:[[sum(map(mul,zip(a,b)))for b in zip(*B)]for a in A]) adalah implementasi langsung dari perkalian matriks. Outer lambda ( lambda A,n:reduce(...,[A]*n,identity_matrix(len(A)))) digunakan reduceuntuk menghitung kekuatan matriks dengan perkalian matriks berulang (menggunakan fungsi perkalian matriks buatan sendiri yang disebutkan di atas), dengan matriks identitas sebagai nilai awal untuk mendukung n=0.

Mego
sumber
2

Julia, 90 86 68 byte

f(A,n)=n<1?eye(A):[A[i,:][:]⋅f(A,n-1)[:,j]for i=m=1:size(A,1),j=m]

Ini adalah fungsi rekursif yang menerima matriks ( Array{Int,2}) dan integer dan mengembalikan matriks.

Tidak Disatukan:

function f(A, n)
    if n < 1
        # Identity matrix with the same type and dimensions as the input
        eye(A)
    else
        # Compute the dot product of the ith row of A and the jth column
        # of f called on A with n decremented
        [dot(A[i,:][:], f(A, n-1)[:,j]) for i = (m = 1:size(A,1)), j = m]
    end
end

Cobalah online! (termasuk semua kecuali test case terakhir, yang terlalu lambat untuk situs)

Disimpan 18 byte berkat Dennis!

Alex A.
sumber
2

Python 2.7, 158 145 byte

Jawaban terburuk di sini, tapi golf terbaik saya di Python. Setidaknya itu menyenangkan belajar bagaimana melakukan perkalian matriks.

Golf:

def q(m,p):
 r=range(len(m))
 if p<1:return[[x==y for x in r]for y in r]
 o=q(m,p-1)
 return[[sum([m[c][y]*o[x][c]for c in r])for y in r]for x in r]

Penjelasan:

#accepts 2 arguments, matrix, and power to raise to
def power(matrix,exponent):
 #get the range object beforehand
 length=range(len(matrix))
 #if we are at 0, return the identity
 if exponent<1:
  #the Boolean statement works because Python supports multiplying ints by bools
  return [[x==y for x in length] for y in length]
 #otherwise, recur
 lower=power(matrix,exponent-1)
 #and return the product
 return [[sum([matrix[c][y]*lower[x][c] for c in length]) for y in length] for x in length]
Biru
sumber
1

JavaScript (ES6), 123 byte

(n,a)=>[...Array(n)].map(_=>r=m(i=>m(j=>m(k=>s+=a[i][k]*r[k][j],s=0)&&s)),m=g=>a.map((_,n)=>g(n)),r=m(i=>m(j=>+!(i^j))))&&r

Saya menggunakan versi 132 byte reducetetapi saya asering memetakannya sehingga ternyata 9 byte lebih pendek untuk menulis fungsi pembantu untuk melakukannya untuk saya. Bekerja dengan menciptakan matriks identitas dan mengalikannya dengan atulisan tangan nkali. Ada sejumlah ekspresi yang mengembalikan 0atau 1untuk i == jtetapi mereka semua tampak sepanjang 7 byte.

Neil
sumber
1

Python 3 , 147 byte

def f(a,n):
 r=range(len(a));r=[[i==j for j in r]for i in r]
 for i in range(n):r=[[sum(map(int.__mul__,x,y))for y in zip(*a)]for x in r]
 return r

Cobalah online!

Biarawati Bocor
sumber
1

R, 49 byte

f=function(m,n)`if`(n,m%*%f(m,n-1),diag(nrow(m)))

Fungsi rekursif yang membutuhkan matrix dan kekuatan nuntuk menaikkannya. Panggilan secara rekursif %*%, yang menghitung titik-produk. Nilai awal untuk rekursi adalah matriks identitas dengan ukuran yang sama dengan m. Karena m %*% m = m %*% m %*% I, ini berfungsi dengan baik.

JAD
sumber
0

Python 2 , 131 byte

f=lambda M,n:n and[[sum(map(int.__mul__,r,c))for c in zip(*f(M,n-1))]for r in M]or[[0]*i+[1]+[0]*(len(M)+~i)for i in range(len(M))]

Cobalah online!

Arfie
sumber