9
$\begingroup$

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
enter image description here

find positions of following pattern :
enter image description here

answer :
enter image description here

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 enter image description here
  3. The process or results do not have to appear visually. I just need to get the coordinates.
$\endgroup$
3
  • 3
    $\begingroup$ Include your list as Mathematica code. $\endgroup$
    – MarcoB
    Jun 12 at 12:42
  • 3
    $\begingroup$ 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. $\endgroup$ Jun 12 at 13:03
  • $\begingroup$ Thank you, I undertood ListCorrelate, it uses multiplication and addition. Can this applied to find more complicated fixed pattern of 0s and 1s ? $\endgroup$
    – imida k
    Jun 12 at 13:30

3 Answers 3

12
$\begingroup$

You could use ArrayFilter:

NeighborhoodPattern = {{1, _}, {1, 1}};
matchingNeighborhoods = 
  ArrayFilter[
    MatchQ[NeighborhoodPattern], 
    testData, 
    {{1, 1}, {1, 1}}, 
    Padding -> None]

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

enter image description here

$\endgroup$
1
  • $\begingroup$ Thank you, I want to make my own one in the future. $\endgroup$
    – imida k
    Jun 22 at 14:00
10
$\begingroup$

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

enter image description here

$\endgroup$
7
$\begingroup$

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}};
around = ArrayPad[arr,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}]& //
TraditionalForm

we can see the 1 in arr, that's the position.

arr +around[[;;-3,2;;-2]]+around[[ 2;;-2,3;;]] // Position[3]

{{3, 1}, {4, 3}, {5, 6}, {6, 3}, {7, 4}}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.