algorithm - Group Python list of lists into groups based on overlapping items

Question

I have a list of lists and I am trying to group or cluster them based on their items. A nested list starts a new group if none of the elements are in the previous group.

Input:

paths = [  
        ['D', 'B', 'A', 'H'],  
        ['D', 'B', 'A', 'C'],  
        ['H', 'A', 'C'],  
        ['E', 'G', 'I'],  
        ['F', 'G', 'I']]

My failed Code:

paths = [
    ['D', 'B', 'A', 'H'],
    ['D', 'B', 'A', 'C'],
    ['H', 'A', 'C'],
    ['E', 'G', 'I'],
    ['F', 'G', 'I']
]
groups = []
paths_clone = paths
for path in paths:
    for node in path:
        for path_clone in paths_clone:
            if node in path_clone:
                if not path == path_clone:
                    groups.append([path, path_clone])
                else:
                    groups.append(path)
print groups

Expected Output:

[
 [
  ['D', 'B', 'A', 'H'],
  ['D', 'B', 'A', 'C'],
  ['H', 'A', 'C']
 ],
 [
  ['E', 'G', 'I'],
  ['F', 'G', 'I']
 ]
]

Another Example:

paths = [['shifter', 'barrel', 'barrel shifter'],
         ['ARM', 'barrel', 'barrel shifter'],
         ['IP power', 'IP', 'power'],
         ['ARM', 'barrel', 'shifter']]

Expected Output Groups:

output = [
         [['shifter', 'barrel', 'barrel shifter'],
         ['ARM', 'barrel', 'barrel shifter'],
         ['ARM', 'barrel', 'shifter']],
         [['IP power', 'IP', 'power']],
         ]

Answer 1

As with most questions in Python that start with "I'm trying to group… by foo…", the answer is "Use itertools.groupby with foo as a key."

---

First, let's take a very simple grouping criterion: length of each list. For that, the key function is just len. (You may also want to sort first, probably with the same key, depending on your data.)

groups = [list(group) for key, group in itertools.groupby(paths, len)]

---

Sometimes defining the grouping criterion (and therefore key function) is hard, or impossible, to define in terms of an independent transformation on each element. In those cases, groupby is generally not the answer (although groupby plus another itertools function still might be).

In this case, the most natural way to define the grouping criterion is by comparison with adjacent elements. The easiest way to write that is to write a cmp function that compares two adjacent elements, and then use functools.cmp_to_key on it:

def cmp_paths(lhs, rhs):
    return 0 if any(key in lhs for key in rhs) else -1
key_paths = functools.cmp_to_key(cmp_paths)
groups = [list(group) for key, group in itertools.groupby(paths, key_paths)]