19

I have a list of lists, something like

[[1, 2, 3,],[4, 5, 6,],[7, 8, 9]].

Represented graphically as:

1 2 3
4 5 6
7 8 9

I'm looking for an elegant approach to check the value of neighbours of a cell, horizontally, vertically and diagonally. For instance, the neighbours of [0][2] are [0][1], [1][1] and [1][2] or the numbers 2, 5, 6.

Now I realise, I could just do a bruteforce attack checking every value a la:

[i-1][j]
[i][j-1]
[i-1][j-1]
[i+1][j]
[i][j+1]
[i+1][j+1]
[i+1][j-1]
[i-1][j+1]

But thats easy, and I figured I can learn more by seeing some more elegant approaches.

2
  • Do you want to get the indices or the values? And do you want a function that can do random access on every index or a function that returns a list of (val, neighbors_of_val) pairs? -- Just getting the indices is too simple for a elegant solution, but what you really want to do might be more interesting Oct 25, 2009 at 13:48
  • 1
    Either or - I deliberately left this question fairly general so people wouldn't feel constrained. Oct 25, 2009 at 13:49

16 Answers 16

31
# Size of "board"
X = 10
Y = 10

neighbors = lambda x, y : [(x2, y2) for x2 in range(x-1, x+2)
                               for y2 in range(y-1, y+2)
                               if (-1 < x <= X and
                                   -1 < y <= Y and
                                   (x != x2 or y != y2) and
                                   (0 <= x2 <= X) and
                                   (0 <= y2 <= Y))]

>>> print(neighbors(5, 5))
[(4, 4), (4, 5), (4, 6), (5, 4), (5, 6), (6, 4), (6, 5), (6, 6)]

I don't know if this is considered clean, but this one-liner gives you all neighbors by iterating over them and discarding any edge cases.

5
  • What if the "board" is 10201x10201?
    – FaCoffee
    Nov 22, 2015 at 19:00
  • @CF84: Then the constants X and Y would need to have different values assigned to them. Do you have an issue regarding this—what's your point?
    – martineau
    Jan 26, 2017 at 21:27
  • @CDspace how does the edit deviate from the original intent of the post? If you mean the one-liner, it can still be written on one line with a normal function. Also, it hasn't been a one-liner anyway since the previous edit. At least the uppercase X and Y variables should be changed, since they are hard to spot.
    – skrx
    Feb 28, 2017 at 23:41
  • Why doesn't print(neighbors(10, 9)) return empty set, when I am giving a value out of range?
    – Beats2019
    Jun 20, 2021 at 18:45
  • I think the conditions are wrong. they should be (-1 < x <X) and (-1 < y < Y) and 0 <= x2 <X) and (0 <= y2 < Y). Note omitting = in front of array size X and Y.
    – u tyagi
    Sep 15, 2021 at 10:31
23

Assuming you have a square matrix:

from itertools import product

size = 3

def neighbours(cell):
    for c in product(*(range(n-1, n+2) for n in cell)):
        if c != cell and all(0 <= n < size for n in c):
            yield c

Using itertools.product and thanks to Python's yield expression and star operator, the function is pretty dry but still readable enough.

Given a matrix size of 3, you can then (if needed) collect the neighbours in a list:

>>> list(neighbours((2,2)))
[(1, 1), (1, 2), (2, 1)]

What the function does can be visualized as follows:

Function visualization

2
  • hi, this looks great. But what about an matrix with unequal row and col numbers, like 2*4 array?
    – Xue
    Aug 19, 2020 at 18:04
  • @Xue having the matrix width and height as a tuple, e.g. size = [3, 4] you can check whether c[0] and c[1] are larger than (or equal to) zero and smaller than size[0] and size[1] respectively. E.g. 0 <= i < bound for i, bound in zip(c, size).
    – etuardu
    Dec 9, 2021 at 11:21
12

mb...

from itertools import product, starmap

x, y = (8, 13)
cells = starmap(lambda a,b: (x+a, y+b), product((0,-1,+1), (0,-1,+1)))

// [(8, 12), (8, 14), (7, 13), (7, 12), (7, 14), (9, 13), (9, 12), (9, 14)]
print(list(cells)[1:])
2
  • 1
    I don't understand this answer, and I ran it along with the question's example in Python 2.7. Jul 14, 2012 at 22:34
  • 1
    How would you add a check to make sure the coordinates don't exceed the bounds of the matrix?
    – Ghos3t
    Jul 17, 2020 at 6:57
7
for x_ in range(max(0,x-1),min(height,x+2)):
  for y_ in range(max(0,y-1),min(width,y+2)):
    if (x,y)==(x_,y_): continue
    # do stuff with the neighbours

>>> a=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> width=height=3
>>> x,y=0,2
>>> for x_ in range(max(0,x-1),min(height,x+2)):
...   for y_ in range(max(0,y-1),min(width,y+2)):
...     if (x,y)==(x_,y_): continue
...     print a[x_][y_]
... 
2
5
6
5

If someone is curious about alternative way to pick direct (non-diagonal) neighbors, here you go:

neighbors = [(x+a[0], y+a[1]) for a in 
                    [(-1,0), (1,0), (0,-1), (0,1)] 
                    if ( (0 <= x+a[0] < w) and (0 <= y+a[1] < h))]
2

There's no cleaner way to do this. If you really want you could create a function:

def top(matrix, x, y):
     try:
         return matrix[x][y - 1];
     except IndexError:
         return None
3
  • @ Kaizer.se: Thanks, wasn't sure which one it was and too lazy to look it up or try it. Oct 25, 2009 at 18:06
  • +1 this is not a complete solution, but interesting since that could be quite a Pythonic way to search for neighbors -- it's EAFP Oct 25, 2009 at 19:38
  • This actually won't work. I was doing a similar solution and realized this. Negative indexes actually used for looking up the index in reverse order. For example -1 means the last element.
    – Ege Aydın
    Mar 27, 2019 at 4:54
1

Here is your list:

(x - 1, y - 1) (x, y - 1) (x + 1, y - 1)
(x - 1, y)     (x, y)     (x + 1, y)
(x - 1, y + 1) (x, y + 1) (x + 1, y + 1)

So the horizontal neighbors of (x, y) are (x +/- 1, y).

The vertical neighbors are (x, y +/- 1).

Diagonal neighbors are (x +/- 1, y +/- 1).

These rules apply for an infinite matrix. To make sure the neighbors fit into a finite matrix, if the initial (x, y) is at the edge, just apply one more restriction to the coordinates of neighbors - the matrix size.

0
>>> import itertools
>>> def sl(lst, i, j):
    il, iu = max(0, i-1), min(len(lst)-1, i+1)
    jl, ju = max(0, j-1), min(len(lst[0])-1, j+1)
    return (il, iu), (jl, ju)

>>> lst = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> tup = 0, 2
>>> [lst[i][j] for i, j in itertools.product(*sl(lst, *tup)) if (i, j) != tup]
[2, 5, 6]

I don't know how elegant it seems to you, but it seems to work w/o any hard-coding.

0

This generates all indices:

def neighboring( array ):
    nn,mm = len(array), len(array[0])
    offset = (0,-1,1) # 0 first so the current cell is the first in the gen
    indices = ( (i,j) for i in range(nn) for j in range(mm) )
    for i,j in indices:
        all_neigh =  ( (i+x,j+y) for x in offset for y in offset )
        valid = ( (i,j) for i,j in all_neigh if (0<=i<nn) and (0<=j<mm) ) # -1 is a valid index in normal lists, but not here so throw it out
        yield valid.next(), valid ## first is the current cell, next are the neightbors

for (x,y), neigh in neighboring( l ):
    print l[x][y], [l[x][y] for x,y in neigh]
0

If lambdas daunt you here you are .But lambdas make your code look clean.@johniek_comp has a very clean solution TBH

k,l=(2,3)
x = (0,-1,+1)
y = (0,-1,+1)
cell_u = ((k+a,l+b) for a in x for b in y)
print(list(cell_u))
0

Inspired by one of the previous answers.

You can use min() and max() functions to shorten the calculations:

width = 3
height = 3

[(x2, y2) for x2 in range(max(0, x-1), min(width, x+2)) 
                    for y2 in range(max(0, y-1), min(height, y+2))
                    if (x2, y2) != (x, y)]
0

Thank you to @JS_is_bad for a great hint about the neighbors. Here is the running code for this problem:

    def findNeighbours(l,elem):
    #This try is for escaping from unbound error that happens 
    #when we try to iterate through indices that are not in array
    try:
        #Iterate through each item of multidimensional array using enumerate
        for row,i in enumerate(l):
            try:
                #Identifying the column index of the givem element
                column=i.index(elem)
            except ValueError:
                continue
            x,y=row,column
    
    #    hn=list(((x,y+1),(x,y-1))) #horizontal neighbours=(x,y+/-1)
    #    vn=list(((x+1,y),(x-1,y))) #vertical neighbours=(x+/-1,y)
    #    dn=list(((x+1,y+1),(x-1,y-1),(x+1,y-1),(x-1,y+1))) #diagonal neighbours=(x+/-1,y+/-1)
        #Creating a list with values that are actual neighbors for the extracted index of array
        neighbours=[(x,y+1),(x,y-1),(x+1,y),(x-1,y),(x+1,y+1),(x-1,y-1),(x+1,y-1),(x-1,y+1)]
        #Creating a universe of indices from given array
        index_list=[(i,j) for i in range(len(l)) for j in range(len(l[i]))]
        #Looping through index_list and nested loop for neighbours but filter for matched ones
        # and extract the value of respective index
        return_values=[l[index[0]][index[1]] for index in index_list for neighbour in neighbours if index==neighbour]
        return return_values,neighbours
    except UnboundLocalError:
        return []
0

Inspired by johniek's answer here is my solution which also checks for boundaries.

def get_neighbours(node, grid_map):
   row_index, col_index = node
   height, width = len(grid_map), len(grid_map[0])
   cells = list(starmap(lambda a, b: (row_index + a, col_index + b), product((0, -1, +1), (0, -1, +1))))
   cells.pop(0) #  do not include original node
   cells = list(filter(lambda cell: cell[0] in range(height) and cell[1] in range(width), cells))
   return cells
0
def numCells(grid):
    x=len(grid)
    y=len(grid[0])
    c=0
    for i in range(x):
        for j in range(y):
            value_=grid[i][j]
            f=1
            for i2 in range(max(0,i-1),min(x,i+2)):
                for j2 in range(max(0,j-1),min(y,j+2)):
                    if (i2,j2) != (i,j) and value_<=grid[i2][j2]:
                        flag=0
                        break
                if flag ==0:
                    break
                else:
                    c+=1
    return c
1
  • This determines the number of neighbours, if I understand it correctly, which isn't what the question is asking. May 13, 2022 at 19:53
0
def getNeighbors(matrix: list, point: tuple):
    neighbors = [] 
    m = len(matrix)
    n = len(matrix[0])
    x, y = point 
    for i in range (x -1, x +2): #prev row to next row
        for j in range(y - 1, y +2): #prev column to next col 
            if (0 <= i < m) and (0 <= j < n): 
                neighbors.append((i,j))
    return neighbors
-1

maybe you are checking a sudoku box. If the box is n x n and current cell is (x,y) start checking:

startingRow = x / n * n;
startingCol = y/ n * n

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.