Group Python list of lists into groups based on overlapping items

algorithm, list, python

Solution

You are grouping based on sets, so use a set to detect new groups:

def grouper(sequence):
    group, members = [], set()

    for item in sequence:
        if group and members.isdisjoint(item):
            # new group, yield and start new
            yield group
            group, members = [], set()
        group.append(item)
        members.update(item)

    yield group

This gives:

>>> for group in grouper(paths):
...     print group
... 
[['D', 'B', 'A', 'H'], ['D', 'B', 'A', 'C'], ['H', 'A', 'C']]
[['E', 'G', 'I'], ['F', 'G', 'I']]

or you could cast it to a list again:

output = list(grouper(paths))

This assumes that the groups are contiguous. If you have disjoint groups, you need to process the whole list and loop over all groups constructed so far for each item:

def grouper(sequence):
    result = []  # will hold (members, group) tuples

    for item in sequence:
        for members, group in result:
            if members.intersection(item):  # overlap
                members.update(item)
                group.append(item)
                break
        else:  # no group found, add new
            result.append((set(item), [item]))

    return [group for members, group in result]

Problem

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']], ] ```

Original source