3
$\begingroup$

I want to be able to implement a rule that extracts the von Neumann neighbors from a given list of lists, that act as the entries of a rectangular matrix.

Say a list of lists is given:

{{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}

I want to be able to read each element as "a" terms with subscripts i and j so that the list of lists is really

{{a1,1,a1,2,a1,3,a1,4},{a2,1,a2,2,a2,3,a2,4},{a3,1,a3,2,a3,3,a3,4},{a4,1,a4,2,a4,3,a4,4}}

The 4x4 matrix is just an example - ideally, I want to be able to input any size list of lists, and the underlying "a" terms will expand accordingly. Using this, I can then enter Rule[3,3], where "3,3" is i=3,j=3 (so in the example, 11), and this returns a list of the von Neumann neighbors (in this case, {7,10,12,15}).

My main question here is: How do I automatically map an input list of lists to their underlying terms, in terms of the subscripts i and j?

Thanks

$\endgroup$
0

1 Answer 1

3
$\begingroup$

So, there's the "from the ground up" approach, where we build the list of neighbors "by hand", maybe in some way making use of the following function:

(* This gets the list element A[[i,j]], unless it's out of bounds, in which case it returns Nothing:*)
maybeGetPart[A_, {i_, j_}] := Quiet[Check[A[[i,j]], Nothing, Part::partw], Part::partw]

(* This gets the list of neighbors around part i,j for an array A: *)
getNeighbors[A_, {i_, j_}] :=
     {maybeGetPart[A, {i - 1, j}], 
      maybeGetPart[A, {i + 1, j}], 
      maybeGetPart[A, {i, j - 1}], 
      maybeGetPart[A, {i, j + 1}]}

(*Gets the list of neighbors around each point in A: *)
NeighborList0[A_] := Table[getNeighbors[A,{i,j}], {i, Dimensions[A][[1]]}, {j, Dimensions[A][[2]]}]

Or, instead of doing any of the above, you could simply use ArrayFilter! This is a neat way of getting the list of neighbors:

NeighborList[A_] := ArrayFilter[DeleteMissing[Flatten[#]] &, A, 
                                {{0, 1, 0},
                                 {1, 0, 1},
                                 {0, 1, 0}},
                                Padding -> Missing[]]

The output of this will be a list of lists such that at part i,j of that output, you have the list of neighbors around part i,j of A. E.g., with neighbors = NeighborList[A], neighbors[[i,j]] is the list of neighbors around A[[i,j]].

What this does is get the list of neighbors using the template {{0, 1, 0}, {1, 0, 1}, {0, 1, 0}} (where a 1 is present exactly at the Von Neumann neighbor positions), uses Missing[] as the value for padding at the edge of the list (you can also make it periodic if you want!), and then flattens that list and removes the values of Missing[] via the function DeleteMissing[Flatten[#]] &. (ArrayFilter also inserts Missing[] values at each 0 in the template, so this serves to delete those too.)

Note: if you want to keep track of which neighbor is which, and maybe even preserve a uniform shape for future functions, you can alter DeleteMissing[Flatten[#]] & to your liking. The input it gets at each index is a 3x3 matrix with Missing[] wherever there isn't a neighbor around that index, and the value of the neighbor wherever there is. So, for instance, around 8 in your list above, it would get as input the matrix

{{Missing[], 4        , Missing[]},
 {7        , Missing[], Missing[]},
 {Missing[], 12       , Missing[]}}

As is, it then flattens this list of lists, then removes all the Missing[]s.

Lmk if any of this doesn't make sense or isn't clear! :)

EDIT: Or, check out the nice answer pointed to in Carl Woll's comment that uses Nearest, which is faster than mine by a factor of about 3.5, even when used to build the entire table of neighbors like ArrayFilter does!

$\endgroup$

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