Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
#!/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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.