Intersection Of Tuples In A List - Python

I have a list of tuples like this : all_tuples=[(92, 242),(355, 403),(355, 436),(355, 489),(403, 436),(436, 489),(515, 517),(517, 859),(634, 775),(701, 859),(775, 859)] and I nee

Solution 1:

This is network problem , using networkx

import networkx as nx 
G=nx.Graph()
all_tuples=[(92, 242),(355, 403),(355, 436),(355, 489),(403, 436),(436, 489),(515, 517),(517, 859),(634, 775),(701, 859),(775, 859)]
G.add_edges_from(all_tuples)
list(nx.connected_components(G))
Out[1216]: [{92, 242}, {355, 403, 436, 489}, {515, 517, 634, 701, 775, 859}]

Solution 2:

This solution builds a list of equivalence classes, where being in the same tuple is our equivalence relation. For each tuple, we make a list of all the sets in our list that match some element of that tuple. If there is none, we make a set of that tuple and add it to the list. If there is one, we update that set to include the other items of the tuple. If there are multiple, we remove them from the list, combine them and the tuple unto one set, then add that set to the list.

res = []
for t in all_tuples:
    matched = []
    for s in res:
        if s.intersection(t):
            matched.append(s)
    ifnot matched:
        res.append(set(t))
    eliflen(matched) == 1:
        matched[0].update(t)
    else:
        res = [subl for subl in res if subl notin matched]
        res.append(set.union(*matched, t))

print(res)
# [{242, 92}, {489, 436, 355, 403}, {515, 517, 775, 634, 859, 701}]

Solution 3:

And just cause why not, here's an implementation with with just lists and tuples.

all_tuples=[(92, 242),(355, 403),(355, 436),(355, 489),(403, 436),(436, 489),(515, 517),(517, 859),(634, 775),(701, 859),(775, 859)]

curr_min, curr_max = all_tuples[0]
final= []
intermediate = [curr_min, curr_max]
for next_left, next_right in all_tuples[1:]:
    if curr_max >= next_left:
        intermediate.extend([next_left, next_right])
        curr_min, curr_max =min(curr_min, next_left), max(curr_max, next_right)
    else:
        final.append(set(intermediate))
        intermediate = []
        curr_min, curr_max = next_left, next_right
final.append(set(intermediate))