public
Last active

  • Download Gist
3744048.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
#!/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()

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.