How Can I Get Union Of 2d List Items When There Occurs Any Intersection (in Efficient Way)?

I have 2D list in python list = [[9, 2, 7], [9, 7], [2, 7], [1, 0], [0, 5, 4]] I would like to get union of list items if there occurs any intersection. For example [9, 2, 7], [9,

Solution 1:

Here is a theoretical answer: This is a connected component problem: you build a graph as follows:

• there is a vertex for each set is the list
• there is an edge between two sets when they have a common value.

what you want is the union of the connected components of the graph.

Solution 2:

You have a graph problem. You want to build connected components in a graph whose vertices are elements of your sublists, and where two vertices have an edge between them if they're elements of the same sublist. You could build an adjacency-list representation of your input and run a graph search algorithm over it, or you could iterate over your input and build disjoint sets. Here's a slightly-modified connected components algorithm I wrote up for a similar question:

import collections

# build an adjacency list representation of your input
graph = collections.defaultdict(set)
for l in input_list:
    if l:
        first = l[0]
        for element in l:
            graph[first].add(element)
            graph[element].add(first)

# breadth-first search the graph to produce the output
output = []
marked = set() # a set of all nodes whose connected component is knownfor node in graph:
    if node notin marked:
        # this node is not in any previously seen connected component# run a breadth-first search to determine its connected component
        frontier = set([node])
        connected_component = []
        while frontier:
            marked |= frontier
            connected_component.extend(frontier)

            # find all unmarked nodes directly connected to frontier nodes# they will form the new frontier
            new_frontier = set()
            for node in frontier:
                new_frontier |= graph[node] - marked
            frontier = new_frontier
        output.append(tuple(connected_component))

Solution 3:

Here is an answer without any imports:

deffunc(L):
    r = []
    cur = set()
    for l in L:
        ifnot cur:
            cur = set(l)
        ifany(i in cur for i in l):
            cur.update(l)
        else:
            r.append(cur)
            cur = set(l)
    r.append(cur)
    whilelen(r)>1:
        ifany(i in r[0] for i in r[-1]):
            r[-1].update(r.pop(0))
        else:
            breakreturn r

Using it:

>>> func([[9, 2, 7], [9, 7], [2, 7], [1, 0], [0, 5, 4]])
[set([9, 2, 7]), set([0, 1, 4, 5])]
>>> func([[0],[1],[2],[0,1]])
[set([2]), set([0, 1])]

---

You can remove the set and return a list of lists by changing r.append(cur) into r.append(list(cur)), but I think it is neater to return sets.

Solution 4:

This one uses sets:

>>> l = [[9, 2, 7], [9, 7], [2, 7], [1, 0], [0, 5, 4]]
>>> done = []
>>> whilelen(done) != len(l):
    start = min([i for i inrange(len(l)) if i notin done])
    ref = set(l[start])
    for j in [i for i inrange(len(l)) if i notin done]:
        ifset(l[j]) & ref:
            done.append(j)
            ref |= set(l[j])
    print ref


set([2, 7, 9])
set([0, 1, 4, 5])

Solution 5:

I propose that you examine each pair of list with itertools

import itertools, numpy

ls_tmp_rmv = []

whileTrue:
    ls_tmp = []

    for s, k in itertools.combinations(lisst, 2):
        iflen(set(s).intersection( set(k) )) > 0:

            ls_tmp = ls_tmp + [numpy.unique(s + k).tolist()]

            if [s] notin ls_tmp:
                ls_tmp_rmv = ls_tmp_rmv + [s]
            if [k] notin ls_tmp:
                ls_tmp_rmv = ls_tmp_rmv + [k]
        else:
            ls_tmp = ls_tmp + [s] + [k]

    ls_tmp = [ls_tmp[i] for i inrange(len(ls_tmp)) if ls_tmp[i] 
                    notin ls_tmp[i+1:]]
    ls_tmp_rmv = [ls_tmp_rmv[i] for i inrange(len(ls_tmp_rmv)) 
                     if ls_tmp_rmv[i] notin ls_tmp_rmv[i+1:]]

    ls_tmp = [X for X in ls_tmp if X notin ls_tmp_rmv]

    if ls_tmp == lisst :
        breakelse:
        lisst = ls_tmp

print lisst

You take all combinations of all pairs of lists in your list and check whether there are elements in common. If so, you merge the pair. If not, you add both peers in the pair. You keep in mind the elements you merged to remove them from the resulting list in the end.

With the list

lisst = [[1,2], [2,3], [8,9], [3,4]]

you do get

[[1, 2, 3, 4], [8, 9]]