Merge lists that share common elements

by

You can see your list as a notation for a Graph, ie ['a','b','c'] is a graph with 3 nodes connected to each other. The problem you are trying to solve is finding connected components in this graph.

You can use NetworkX for this, which has the advantage that it’s pretty much guaranteed to be correct:

l = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]

import networkx 
from networkx.algorithms.components.connected import connected_components


def to_graph(l):
    G = networkx.Graph()
    for part in l:
        # each sublist is a bunch of nodes
        G.add_nodes_from(part)
        # it also imlies a number of edges:
        G.add_edges_from(to_edges(part))
    return G

def to_edges(l):
    """ 
        treat `l` as a Graph and returns it's edges 
        to_edges(['a','b','c','d']) -> [(a,b), (b,c),(c,d)]
    """
    it = iter(l)
    last = next(it)

    for current in it:
        yield last, current
        last = current    

G = to_graph(l)
print connected_components(G)
# prints [['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]

To solve this efficiently yourself you have to convert the list into something graph-ish anyways, so you might as well use networkX from the start.

More Related Contents:

  1. How to merge lists into a list of tuples?
  2. merging Python dictionaries
  3. Merging dictionary value lists in python
  4. How to merge multiple lists into one list in python? [duplicate]
  5. How do I merge multiple lists into one list? [duplicate]
  6. How to zip two lists of lists
  7. finding the biggest sequence of repeating numbers in a list
  8. How to append new line to the list
  9. cartesian product in pandas
  10. Remove duplicate dict in list in Python
  11. How to efficiently compare two unordered lists (not sets) in Python?
  12. Filtering a list of strings based on contents
  13. Convert tuple to list and back
  14. Unpacking a list / tuple of pairs into two lists / tuples
  15. Python 3 turn range to a list
  16. Call int() function on every list element?
  17. Split list into smaller lists (split in half)
  18. Find nearest indices for one array against all values in another array – Python / NumPy
  19. Splitting on last delimiter in Python string?
  20. Transform “list of tuples” into a flat list or a matrix
  21. Inserting a value into all possible locations in a list
  22. Find the index of an item in a list of lists
  23. Slicing list of lists in Python
  24. Replacing a sublist with another sublist in python
  25. How to get the cartesian product of multiple lists
  26. Union find implementation using Python
  27. Check if all values in list are greater than a certain number
  28. python – get list of tuples first index?
  29. Creating a list in Python- something sneaky going on?
  30. Rearranging list based on order of another list

Leave a Comment