Determining neighbours of cell two dimensional list

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.

17 Answers

# 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.

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:

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:]) 

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 

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

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 

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.

>>> 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.

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] 

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)) 

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

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

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 

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 

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 

# Get the neighbour elements from itertools import product def neighbours(arr, *coordinate): x, y=coordinate[0], coordinate[1] row=[i for i in range(x-1,x+2) if 0<=i<len(arr)] col=[i for i in range(y-1,y+2) if 0<=i<len(arr[0])] neighbours= set(product(row,col))-{(x,y)} return [arr[val[0]][val[1]] for val in neighbours] # Example: arr=[[1,2,3],[4,5,6],[7,8,9]] # 1 2 3 # 4 5 6 # 7 8 9 print(neighbours(arr,0,0)) print(neighbours(arr,0,1)) print(neighbours(arr,1,1)) # Output [2, 4, 5] [6, 1, 5, 3, 4] [2, 6, 8, 1, 7, 3, 9, 4] arr2=[[12,34,12,54],[23,23,11,44],[76,67,87,22],[13,78,45,22],[55,77,33,87]] # 12 34 12 54 # 23 23 11 44 # 76 67 87 22 # 13 78 45 22 # 55 77 33 87 print(neighbours(arr2,0,0)) print(neighbours(arr2,2,2)) print(neighbours(arr2,4,3)) # Output [34, 23, 23] [11, 67, 78, 23, 22, 22, 45, 44] [45, 22, 33] 

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