Count number of occurrences of an array without overlap in another array

Question

I have a mxn matrix A, where m%t = n%t = 0, so that a smaller txt matrix B tiles the matrix without borders or overlaps. I want to check if A consists entirely of tiles from B without calculating a tiling as an intermediate step as efficiently as possible. Furthermore for my special use case, it is not necessary to know B. It is enough to test if A strictly repeats itself every txt tile in every direction.

Numeric examples:

A = [[1, 0, 1, 0],
     [0, 1, 0, 1],
     [1, 0, 1, 0],
     [0, 1, 0, 1]]
B.shape = [2,2]
--> True
B.shape = [1,1]
--> False

So far, I calculate a comparison matrix C, which simply is a tiling of B to fit the size of A:

import numpy as np
x,y      = B.shape
x_a, y_a = A.shape
x_t = x_a/x
y_t = y_a/y
B_dash = A[:x, :y]
C = np.tile(B_dash,(x_t, y_t))
np.count_nonzero(A-C)

Is there a faster way, without calculating C?

Answer 1

Appproach #1 : It seems we are counting the number of occurrences of B in A as distinct blocks. So, we can use skimage.util.view_as_blocks -

from skimage.util import view_as_blocks as viewW

out = np.count_nonzero((viewW(A, B.shape) == B).all((2,3)))

Appproach #2 : Staying with NumPy, we would have -

m1,n1 = A.shape
m2,n2 = B.shape
out = np.count_nonzero((A.reshape(m1//m2,m2,n1//n2,n2) == B[:,None]).all((1,3)))

Sample runs -

In [274]: A
Out[274]: 
array([[2, 0, 2, 0],
       [5, 3, 5, 1],
       [3, 3, 2, 6],
       [1, 0, 3, 1]])

In [275]: B
Out[275]: 
array([[3, 3],
       [1, 0]])

In [276]: np.count_nonzero((viewW(A, B.shape) == B).all((2,3)))
Out[276]: 1



In [278]: A
Out[278]: 
array([[2, 0, 3, 3],
       [5, 3, 1, 0],
       [3, 3, 2, 6],
       [1, 0, 3, 1]])

In [279]: B
Out[279]: 
array([[3, 3],
       [1, 0]])

In [280]: np.count_nonzero((viewW(A, B.shape) == B).all((2,3)))
Out[280]: 2