Group recursively adjacent tuples from a list in Python

Question

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 ?

Answer 1

If I understood correctly.

a = [(1, 1), (3, 1), (4, 5), (8, 8), (4, 4), (8, 9), (2, 1)]
a = sorted(a)
def Manhattan(tuple1, tuple2):
    return abs(tuple1[0] - tuple2[0]) + abs(tuple1[1] - tuple2[1])


result = [set()]
l = len(a)
for i, v in enumerate(a):
    if not i+1 >= l:
        if Manhattan(v, a[i+1]) ==1:
            result[-1].add(v)
            result[-1].add(a[i+1])
        else:
            result.append(set())
            result[-1].add(a[i+1])
print(result)

Output:

[{(3, 1), (1, 1), (2, 1)}, {(4, 5), (4, 4)}, {(8, 9), (8, 8)}]

Answer 2

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)

Answer 3

A completely different, maybe less efficient but certainly interesting approach, would be with a graph theoretic formulation. You can view this problem as finding all connected components of a graph where two vertices are connected whenever the Manhattan distance is one. Crudely written, you could do :

import networkx as nx

G = nx.Graph()
a = [(1, 1), (3, 1), (4, 5), (8, 8), (4, 4), (8, 9), (2, 1)]
n = len(a)
G.add_nodes_from(a)

# Generate edges
for i in range(n):
    for j in range(i+1,n):
        if Manhattan(a[i],a[j]) == 1:
            G.add_edge(a[i], a[j])

# Find components
components = nx.connected_components(G)
for x in components:
    print(x)

which spits out

{(3, 1), (1, 1), (2, 1)}
{(4, 5), (4, 4)}
{(8, 9), (8, 8)}