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 need to take the intersection of all tuples and union them.
The desired result = [{92, 242},{355, 403,436,489},{515, 517,859,701,775,634}]
That is the intersected tuples are union iteratively.
I tried to convert the tuples to sets and then take the intersection but did not work. Any idea?
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}]
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)
if not matched:
res.append(set(t))
elif len(matched) == 1:
matched[0].update(t)
else:
res = [subl for subl in res if subl not in matched]
res.append(set.union(*matched, t))
print(res)
# [{242, 92}, {489, 436, 355, 403}, {515, 517, 775, 634, 859, 701}]
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))
