проблема

Создайте программу или функцию, которая может вычислить результат матрицы, возведенной в n- ^ую степень. Ваш код возьмет произвольную квадратную матрицу A и неотрицательное целое число n и вернет матрицу со значением A ⁿ .

ограничения

Встроенные функции, которые вычисляют мощность матрицы и матричное произведение, не допускаются.

Остальные стандартные правила для code-golf применяются.

объяснение

Для данной квадратной матрицы A значение A ⁿ = AA ⋯ A (повторное матричное произведение A на себя, n раз). Если n положительно, используется только что упомянутый стандарт. Когда n равно нулю, единичная матрица с тем же порядком A является результатом.

Цель

Это код-гольф, и выигрывает самый короткий код.

Тестовые случаи

Здесь A - входная матрица, n - входное целое число, а r - выходная матрица, где r = A ⁿ .

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

Желе , 17 16 15 байт

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

Попробуйте онлайн!

Постоянные ссылки с выходом сетки: контрольный пример 1 | контрольный пример 2 | контрольный пример 3 | контрольный пример 4 | контрольный пример 5

Как это работает

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.

MATL , 20 байтов

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

Попробуйте онлайн!

объяснение

Это позволяет избежать умножения матриц, делая это вручную, используя поэлементное умножение с широковещательной передачей, за которой следует векторизованная сумма. В частности, чтобы умножить матрицы Mи Nоба размера s × s :

1. Транспонировать M. Назовите полученную матрицу P.
2. Перестановка размеров Nтаких, которые N«повернуты» с осью вращения вдоль первого измерения, давая , скажем, трехмерный массив s × 1 × sQ .
3. Умножьте каждый элемент на Pкаждый элемент Qс неявной трансляцией. Это означает, что Pона автоматически реплицируется s раз по третьему измерению и sQ повторяется по второму, чтобы сделать их s × s × s до того, как произойдет фактическое поэлементное умножение.
4. Суммируйте по первому измерению, чтобы получить массив 1 × s × s .
5. Сожмите ведущее одноэлементное измерение, чтобы получить результат s × s .

Код комментария:

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

APL, 32 31 символ

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

Левый аргумент - сила, которую нужно поднять, правый - матрица. Самым сложным (наиболее трудоемким) битом является построение единичной матрицы для случая, когда искомый показатель равен 0. Фактическое вычисление основано на том факте, что обобщенный внутренний продукт ( .) с операндами +и в ×качестве операндов фактически является продуктом матрицы. Это в сочетании с ⍣оператором питания («повторить») образует основу решения.

Sage, 112 байт

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

Попробуйте онлайн

Объяснение:

Внутренняя лямбда ( lambda A,B:[[sum(map(mul,zip(a,b)))for b in zip(*B)]for a in A]) является прямой реализацией умножения матриц. Внешняя лямбда ( lambda A,n:reduce(...,[A]*n,identity_matrix(len(A)))) использует reduceдля вычисления мощности матрицы с помощью повторного умножения матриц (используя вышеупомянутую функцию умножения самодельных матриц) с единичной матрицей в качестве начального значения для поддержки n=0.

Юлия, 90 86 68 байт

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

Это рекурсивная функция, которая принимает матрицу ( Array{Int,2}) и целое число и возвращает матрицу.

Ungolfed:

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

Попробуйте онлайн! (включает все тесты, кроме последнего, что слишком медленно для сайта)

Благодаря Деннису сэкономлено 18 байт!

Python 2,7, 158 145 байтов

Худший ответ здесь, но мой лучший гольф в Python пока. По крайней мере, было весело учиться умножению матриц.

Golfed:

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]

Объяснение:

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

JavaScript (ES6), 123 байта

(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

Я использовал 132-байтовую версию, reduceно я aтак часто отображал ее, что оказалось на 9 байт короче, чтобы написать вспомогательную функцию, которая сделает это для меня. Работает путем создания матрицы тождественности и умножения ее на aпроизвольные nвремена. Есть несколько выражений, которые возвращают 0или 1для, i == jно все они кажутся длиной 7 байтов.

Python 3 , 147 байт

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

Попробуйте онлайн!

R, 49 байт

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

Рекурсивная функция, которая берет mатрикс и возможность nего поднять. Рекурсивно вызывает %*%, который вычисляет скалярное произведение. Начальным значением для рекурсии является единичная матрица того же размера, что и m. Так как m %*% m = m %*% m %*% I, это работает просто отлично.

Python 2 , 131 байт

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

Попробуйте онлайн!