3744048.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# http://stackoverflow.com/questions/3744048/python-how-to-merge-a-list-into-clusters/3744095#3744095

import itertools

def merge_it(lot):
    """
    >>> merge_it( [(3,4), (18,27), (4,14)] )
    [set([18, 27]), set([3, 4, 14])]
    
    >>> merge_it( [(1,3), (15,21), (1,10), (57,66), (76,85), (66,76)] )
    [set([21, 15]), set([1, 10, 3]), set([57, 66, 76, 85])]

    >>> merge_it( [(1,2), (2,3), (3,4), (4,5), (5,9)] )
    [set([1, 2, 3, 4, 5, 9])]

    >>> merge_it( [()] )
    [set([])]

    >>> merge_it( [(1,)] )
    [set([1])]

    >>> merge_it( [(1,1,2,2)] )
    [set([1, 2])]
    """
    merged = [ set(x) for x in lot ] # operate on sets only
    finished = False
    while not finished:
        finished = True
        for a, b in itertools.combinations(merged, 2):
            if a & b:
                # we merged in this iteration, we may have to do one more
                finished = False
                if a in merged: merged.remove(a)
                if b in merged: merged.remove(b)
                merged.append(a.union(b))
                break
    return merged

if __name__ == '__main__':
    import doctest
    doctest.testmod()