Problem
Erstellen Sie ein Programm oder eine Funktion, die das Ergebnis einer auf die n- te Potenz angehobenen Matrix berechnen kann . Ihr Code nimmt eine beliebige quadratische Matrix A und eine nicht negative ganze Zahl n und gibt eine Matrix mit dem Wert A n zurück .
Beschränkungen
Integrierte Funktionen, die die Matrixleistung und das Matrixprodukt berechnen, sind nicht zulässig.
Es gelten die übrigen Standardregeln für Code-Golf.
Erläuterung
Bei gegebener quadratischer Matrix A ist der Wert von A n = AA ⋯ A (wiederholtes Matrixprodukt von A mit sich selbst, n- mal). Wenn n positiv ist, wird der gerade erwähnte Standard verwendet. Wenn n Null ist, ist die Identitätsmatrix mit der gleichen Ordnung von A das Ergebnis.
Tor
Dies ist Code-Golf und der kürzeste Code gewinnt.
Testfälle
Hier ist A die Eingabematrix, n ist die Eingabe-Ganzzahl und r ist die Ausgabematrix mit 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
quelle
A^-1
als Ersatz für verwendet werdeninv(A)
?exp(k*log(M))
erlaubt? (Obwohl es wegen nicht eindeutiger Zweige möglicherweise nicht funktioniert.)Antworten:
Gelee ,
171615 BytesProbieren Sie es online aus!
Permalinks mit Gitterausgabe: Testfall 1 | Testfall 2 | Testfall 3 | Testfall 4 | Testfall 5
Wie es funktioniert
quelle
MATL , 20 Bytes
Probieren Sie es online aus!
Erläuterung
Dies vermeidet die Matrixmultiplikation, indem sie manuell durchgeführt wird, wobei eine elementweise Multiplikation mit Broadcast gefolgt von einer vektorisierten Summe verwendet wird. Insbesondere zum Multiplizieren von Matrizen
M
undN
beiden der Größe s × s :M
. Rufen Sie die resultierende Matrix aufP
.N
solchen, dieN
mit einer Rotationsachse entlang der ersten Dimension "gedreht" werden, und geben Sie beispielsweise ein s × 1 × s 3D-Array anQ
.P
jedem Element vonQ
mit impliziter Übertragung. Dies bedeutet, dassP
automatisch s- mal entlang der dritten Dimension und s- mal entlang der zweiten DimensionQ
repliziert wird, um beide s × s × s zu machen , bevor die eigentliche elementweise Multiplikation stattfindet.Kommentierter Code:
quelle
APL,
3231 ZeichenLinkes Argument die Macht zu erheben, rechtes Argument die Matrix. Das schwierigste (platzsparendste) Bit ist das Erstellen der Identitätsmatrix für den Fall, dass der gewünschte Exponent 0 ist. Die tatsächliche Berechnung basiert auf der Tatsache, dass das verallgemeinerte innere Produkt (
.
) mit+
und×
als Operanden effektiv das Matrixprodukt ist. Dies bildet zusammen mit dem Power⍣
Operator ("Repeat") das Fleisch der Lösung.quelle
(1+≢⍵)↑1
=>1↑⍨1+≢⍵
um ein Byte zu speichern.Salbei, 112 Bytes
Probieren Sie es online aus
Erläuterung:
Das innere Lambda (
lambda A,B:[[sum(map(mul,zip(a,b)))for b in zip(*B)]for a in A]
) ist eine einfache Implementierung der Matrixmultiplikation. Das äußere Lambda (lambda A,n:reduce(...,[A]*n,identity_matrix(len(A)))
)reduce
berechnet die Matrixleistung durch iterierte Matrixmultiplikation (unter Verwendung der oben genannten hausgemachten Matrixmultiplikationsfunktion), wobei die Identitätsmatrix als zu unterstützender Anfangswert verwendet wirdn=0
.quelle
Julia,
908668 BytesDies ist eine rekursive Funktion, die eine Matrix (
Array{Int,2}
) und eine Ganzzahl akzeptiert und eine Matrix zurückgibt.Ungolfed:
Probieren Sie es online aus! (Beinhaltet alle bis auf den letzten Testfall, der für die Site zu langsam ist)
18 Bytes dank Dennis gespart!
quelle
Python 2.7,
158145 BytesDie schlechteste Antwort hier, aber mein bisher bestes Golf in Python. Zumindest hat es Spaß gemacht zu lernen, wie man Matrixmultiplikation macht.
Golf:
Erläuterung:
quelle
JavaScript (ES6), 123 Byte
Ich hatte eine 132-Byte-Version mit,
reduce
aber ich habe nura
so oft zugeordnet, dass es 9 Bytes kürzer war, eine Hilfsfunktion zu schreiben, um dies für mich zu tun. Funktioniert, indem die Identitätsmatrix erstellt und mita
langenn
Zeiten multipliziert wird . Es gibt eine Reihe von Ausdrücken, die zurückgeben0
oder1
für,i == j
aber alle scheinen 7 Bytes lang zu sein.quelle
Python 3 , 147 Bytes
Probieren Sie es online aus!
quelle
R, 49 Bytes
Rekursive Funktion, die eine
m
Atrix und die Kraft benötigtn
, sie zu erhöhen. Rekursive Aufrufe%*%
, die das Punktprodukt berechnen. Der Anfangswert für die Rekursion ist die Identitätsmatrix mit der gleichen Größe wiem
. Dam %*% m = m %*% m %*% I
funktioniert das ganz gut.quelle
Python 2 , 131 Bytes
Probieren Sie es online aus!
quelle