I have an unsorted list of integer tuples such as:
a = [(1, 1), (3, 1), (4, 5), (8, 8), (4, 4), (8, 9), (2, 1)]
I am trying to find a way to group up the "recursively adjacent" tuples. "Adjacent" are the tuples with Manhattan distance of 1. By "recursively" we means that if A tuple is adjacent to B and B is adjacent to C, then A, B and C should end up in the same group.
The function that returns the Manhattan distance is this:
def Manhattan(tuple1, tuple2):
return abs(tuple1[0] - tuple2[0]) + abs(tuple1[1] - tuple2[1])
The expected result is:
[(1, 1), (2, 1), (3, 1)], [(4, 4), (4, 5)], [(8, 8), (8, 9)]
In this example (1, 1) is adjacent to (2, 1) and (2, 1) to (3, 1) so these three should be grouped up together.
The order doesn't matter so this result is equivalent:
[(3, 1), (2, 1), (1, 1)], [(4, 4), (4, 5)], [(8, 9), (8, 8)]
Are there any ideas on how to solve this ?
a somewhat UnionFind approach, iterating all 1-distanced pairs and "Unifying" their groups:
from itertools import groupby, product
def Manhattan(tuple1, tuple2):
return abs(tuple1[0] - tuple2[0]) + abs(tuple1[1] - tuple2[1])
a = [(1, 1), (3, 1), (4, 5), (8, 8), (4, 4), (8, 9), (2, 1)]
tuple_pairs_with_distance_1 = [sorted(pair) for pair in product(a, repeat=2) if Manhattan(*pair) == 1]
result_dict = {t: {t} for t in a}
for t1, t2 in tuple_pairs_with_distance_1:
# "Unify" these tuple's groups
result_dict[t1] |= result_dict[t2]
result_dict[t2] = result_dict[t1]
result = [[*next(g)] for k, g in groupby(sorted(result_dict.values(), key=id), id)]
print(result)