# What is the best method to search pattern for 2D list?

What is the best method to search patterns for 2D list ? Let L be following 2D-list :

{{0,1,0,1,0,1,1},
{1,0,1,0,1,1,0},
{1,1,1,0,1,0,0},
{1,0,1,1,0,1,1},
{0,0,1,0,1,1,1},
{1,0,1,1,1,0,1},
{1,0,0,1,1,0,1}}


0 1 0 1 0 1 1
1 0 1 0 1 1 0
1 1 1 0 1 0 0
1 0 1 1 0 1 1
0 0 1 0 1 1 1
1 0 1 1 1 0 1
1 0 0 1 1 0 1

We want to find positions of pattern

1 ?
1 1

Check it screenshot:

In

find positions of following pattern :

All 0,1 are related,

Which structure is the best (fast, convinient, widely-used) to do such job?
I've found SparseArray, ArrayPlot, Grid are promising. Also just List (nested list) can be good.
Another candidate is creating a function f and f[1,1]=0, f[1,2]=1,..,f[7,7]=1
Also image based technique can be considered.

For now, I am satisfied with the following condition :

1. there are only 0 or 1 in the 2D-list
2. find completely fixed pattern like
3. The process or results do not have to appear visually. I just need to get the coordinates.
• Include your list as Mathematica code. Jun 12, 2022 at 12:42
• Maybe Position[ListCorrelate[{{1, 0}, {1, 1}}, A], 3] or SparseArray[ UnitStep[ ListCorrelate[{{1, 0}, {1, 1}}, A] - 3]]["NonzeroPositions"], where A is your input array. Jun 12, 2022 at 13:03
• Thank you, I undertood ListCorrelate, it uses multiplication and addition. Can this applied to find more complicated fixed pattern of 0s and 1s ? Jun 12, 2022 at 13:30

You could use ArrayFilter:

NeighborhoodPattern = {{1, _}, {1, 1}};
matchingNeighborhoods =
ArrayFilter[
MatchQ[NeighborhoodPattern],
testData,
{{1, 1}, {1, 1}},


What you have now is a 2D array of True/False, and the length in each dimension is one less than that of testData (I'm assuming that you didn't want your pattern to wrap around the edges, so this should be fine).

The position of the True values indicates the upper left corners of the matching 2x2 neighborhoods:

positions = Position[matchingNeighborhoods, True]
(* {{2, 1}, {3, 3}, {4, 6}, {5, 3}, {6, 4}} *)

Grid[testData, Background -> {None, None, Thread[Rule[positions, LightBlue]]}]


• Thank you, I want to make my own one in the future. Jun 22, 2022 at 14:00

I am sure there are many ways to do it, but here is my take:

alist = {{0, 1, 0, 1, 0, 1, 1}, {1, 0, 1, 0, 1, 1, 0}, {1, 1, 1, 0, 1,
0, 0}, {1, 0, 1, 1, 0, 1, 1}, {0, 0, 1, 0, 1, 1, 1}, {1, 0, 1, 1,
1, 0, 1}, {1, 0, 0, 1, 1, 0, 1}}

mm = {{1, _}, {1, 1}};
(parts = Partition[alist, {2, 2}, 1]) // MatrixForm
Position[parts, mm] (* the required indices *)


Visualization:

hl = {{#[[1]], #[[1]] + 1}, {#[[2]], #[[2]] + 1}} & /@
Position[parts, mm]
thhl = Thread[{# -> Yellow}] & /@ hl
Grid[alist, Background -> {None, None, Sequence @@ # & /@ thhl}]


another array-based method:

arr={{0,1,0,1,0,1,1},
{1,0,1,0,1,1,0},
{1,1,1,0,1,0,0},
{1,0,1,1,0,1,1},
{0,0,1,0,1,1,1},
{1,0,1,1,1,0,1},
{1,0,0,1,1,0,1}};


first, add 0 around the origin matrix.

then

arr
around[[;;-3,2;;-2]]
around[[ 2;;-2,3;;]]


where these 3 arrays are all equal to 1 is the answer.

This means the position of sum == 3

arr +around[[;;-3,2;;-2]]+around[[ 2;;-2,3;;]] //
Map[If[#==3,1,0]&, # ,{2}]& //

we can see the 1 in arr, that's the position.
arr +around[[;;-3,2;;-2]]+around[[ 2;;-2,3;;]] // Position[3]