CODEWITHSUNDEEP
pythonpython-3.xset
practitioner
practitioner

Reputation: 412

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 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?

Upvotes: 3

Views: 1276

Answers (3)

Paritosh Singh
Paritosh Singh

Reputation: 6246

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))

Upvotes: 0

Patrick Haugh
Patrick Haugh

Reputation: 61032

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}]

Upvotes: 2

BENY
BENY

Reputation: 323336

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}]

Upvotes: 9

Related Questions