递归地在 Python 中乘以 2x2 矩阵？没有嵌套循环或 numpy

Question

我很难找到一个将两个 2x2 矩阵递归相乘的非常简单的程序。谁能帮我吗？只需要乘 X 和 Y 而不用 numpy 或使用嵌套循环。

X = [[1, 2],
     [2, 3]]

Y = [[2, 3],
     [3, 4]]

FWIW - 这是我天真的方法:)

X = [[1, 2],  
    [2, 3]]


Y = [[2, 3],  
     [3, 4]]

result = [[0, 0],  
          [0, 0]]

for i in range(len(X)):
    for j in range(len(Y[0])):
        for k in range(len(Y)):
            result[i][j] += X[i][k] * Y[k][j]

for r in result:
    print(r)  

# ANS = [8, 11], [13, 18]

_________________________ 根据下面的评论 - Recursive Strassen 的

import numpy as np
def split(matrix):
    row, col = matrix.shape
    row2, col2 = row // 2, col // 2
    return matrix[:row2, :col2], matrix[:row2, col2:], matrix[row2:, :col2], matrix[row2:, col2:]


def strassen_recur(x, y):
    if len(x) == 1:
        return x * y

    a, b, c, d = split(x)
    e, f, g, h = split(y)

    p1 = strassen_recur(a, f - h)
    p2 = strassen_recur(a + b, h)
    p3 = strassen_recur(c + d, e)
    p4 = strassen_recur(d, g - e)
    p5 = strassen_recur(a + d, e + h)
    p6 = strassen_recur(b - d, g + h)
    p7 = strassen_recur(a - c, e + f)

    c1 = (p5 + p4 - p2 + p6)
    c2 = (p1 + p2)
    c3 = (p3 + p4)
    c4 = (p1 + p5 - p3 - p7)

    c = np.vstack((np.hstack((c1, c2)), np.hstack((c3, c4))))

    return c

print(strassen_recur(x, y))

我也写了一个简单的 Strassen 方法。但就像我提到的，我只是希望有人能快速向我展示一些东西，这样我就不必花很多时间去弄明白了。一切都很好。

Answer 1

如果有人一直在寻找递归解决方案来将两个 2x2... 或 3x3、4x4 矩阵相乘，那么这里就是答案。您只需更改 rows/columns 的数量并添加额外的 for-loops。它不是最漂亮的，但它确实有效。也许有人可以让它变得更好？


X = [[1, 2],
     [2, 3]]

Y = [[2, 3],
     [3, 4]]

result = [[0, 0],
          [0, 0]]
i = 0
j = 0
k = 0

def multiplyMatrixRec(row1, col1, X, row2, col2, Y, result):

    if j < col2:
        if k < col1:
            result[i][j] += X[i][k] * Y[k][j]
            k += 1
            multiplyMatrixRec(row1, col1, X, row2, col2, Y, result)
        j += 1
        multiplyMatrixRec(row1, col1, X, row2, col2, Y, result)
    i += 1
    multiplyMatrixRec(row1, col1, X, row2, col2, Y, result)


def multiplyMatrix(row1, col1, X, row2, col2, Y):
    for i in range(row1):
        for j in range(col2):
            print(result[i][j], end=" ")
        print()

row1 = 2
col1 = 2
row2 = 2
col2 = 2
multiplyMatrix(row1, col1, X, row2, col2, Y)

输出：

8 11
13 18

干杯！

递归地在 Python 中乘以 2x2 矩阵？没有嵌套循环或 numpy

Multiply 2x2 Matrix in Python Recursively? No nested loops or numpy

python

recursion

matrix

multiplication