Recursively find adjacent coordinates for n-dimensional array

user_13041213 0
Viewed 339

For any tuple of coordinates I am given (ex. (2,2) or (1,2,3) or (4,5,6,7,8), etc.), how can I get a list of all the adjacent coordinates.
So that, 

find_adjacents((2,2))    

  >>[[1,1],[1,2],[1,3],[2,1],[2,3],[3,1],[3,2],[3,3]]

and 

find_adjacents((2,2,2,2))

would return something with 3^4-1 elements

You can ignore edge cases for this (imagine indices range from -inf to inf)

tuples recursion list python
2 Answers

You can use itertools.product for this. The Cartesian product of the ranges will include the input itself, so we need to remove it afterwards. list.pop works for this, because the product is generated in order, such that the input itself will always be exactly the middle element.

from itertools import product

def neighbours(t):
    ranges = [(x-1, x, x+1) for x in t]
    result = list(product(*ranges))
    result.pop(len(result) // 2)
    return result

Examples (formatted for readability):

>>> neighbours( (1, 2) )
[(0, 1), (0, 2), (0, 3),
 (1, 1),         (1, 3),
 (2, 1), (2, 2), (2, 3)]

>>> neighbours( (1, 1, 1) )
[(0, 0, 0), (0, 0, 1), (0, 0, 2),
 (0, 1, 0), (0, 1, 1), (0, 1, 2),
 (0, 2, 0), (0, 2, 1), (0, 2, 2),

 (1, 0, 0), (1, 0, 1), (1, 0, 2),
 (1, 1, 0),            (1, 1, 2),
 (1, 2, 0), (1, 2, 1), (1, 2, 2),

 (2, 0, 0), (2, 0, 1), (2, 0, 2),
 (2, 1, 0), (2, 1, 1), (2, 1, 2),
 (2, 2, 0), (2, 2, 1), (2, 2, 2)]
user_122990000

You can use recursion:

def combos(d, c = []):
  if not d:
     yield c
  else:
     yield from [i for b in range(d[0]-1, d[0]+2) for i in combos(d[1:], c+[b])]

vals = (2,2)
print(list(combos(vals)))
print(list(combos((1, 1, 1))))

Output:

[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]
[[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 0], [0, 1, 1], [0, 1, 2], [0, 2, 0], [0, 2, 1], [0, 2, 2], [1, 0, 0], [1, 0, 1], [1, 0, 2], [1, 1, 0], [1, 1, 1], [1, 1, 2], [1, 2, 0], [1, 2, 1], [1, 2, 2], [2, 0, 0], [2, 0, 1], [2, 0, 2], [2, 1, 0], [2, 1, 1], [2, 1, 2], [2, 2, 0], [2, 2, 1], [2, 2, 2]]
user_73267380
Related