Блог

У меня есть такая матрица

 matrix = 
   [
     [1,0,0]
     [0,1,0]
     [0,0,0]
   ]
pattern = 
   [
     [1,0]
     [0,1]
   ]
>>>Should output: Pattern found at index 0
 

Мне нужно найти, есть ли сопоставление шаблона с другой матрицей, заданной во входных данных
Первая матрица может быть MxN, а матрица, указанная во входных данных, должна быть PxQ, где P < M и Q < N.
Я пытался создать вложенные матрицы, а затем сопоставить их с той, которую мне дали на входе, но мне не повезло!
У вас есть какие-либо предложения?

Numpy может создавать эти «подматрицы» для вас, используя np.lib.stride_tricks.sliding_window_view метод. Он принимает в качестве аргументов матрицу и форму меньшей матрицы.

Тогда вам просто нужно использовать np.all , чтобы указать, что все элементы матрицы должны совпадать, чтобы она считалась, и свернуть матрицу формы (2,2,2,2) в форму (2,2) .

 import numpy as np

matrix = np.array([
    [1, 0, 0],
    [0, 1, 0],
    [0, 0, 0],
])
pattern = np.array([
    [1, 0],
    [0, 1]
])

print(np.all(np.all(np.lib.stride_tricks.sliding_window_view(matrix, pattern.shape) == pattern, axis=3), axis=2))
 

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

     [1, 0, 0],
    [0, 1, 0],
    [0, 0, 0],
]
pattern = [
    [1, 0],
    [0, 1]
]


def sliding_window_view(matrix, window_shape):
    h, w = len(matrix), len(matrix[0])
    window_h, window_w = window_shape

    for y in range(h - window_h   1):
        yield [
            [row[x:x   window_w] for row in matrix[y:y   window_h]]
            for x in range(w - window_w   1)
        ]


def find_pattern(matrix, pattern):
    sub_matrices_matrix = sliding_window_view(matrix, (len(pattern), len(pattern[0])))
    for sub_matrices_row in sub_matrices_matrix:
        yield [sub_matrix == pattern for sub_matrix in sub_matrices_row]


print(list(find_pattern(matrix, pattern)))

 

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