Home Original page

[perl-python] exercise: partition a list by equivalence

Paul McGuire ptmcg at austin.rr.com
Thu Feb 24 16:43:12 EST 2005 
A slightly better version, only walks the set of cumulative list of
sets once per pairing.

-- Paul

.    import sets
.
.    input = [[1, 2], [3, 4], [2, 3], [4, 5]]
.    input = [[1, 2], [3, 4], [4, 5]]
.    input = [[1, 2],[2,1], [3, 4], [4, 5],[2,2],[2,3],[6,6]]
.
.def merge(pairings):
.    ret = []
.    for a,b in pairings:
.        aset = None
.        bset = None
.        for s in ret:
.            if not aset and a in s:
.                aset = s
.            if not bset and b in s:
.                bset = s
.            if aset and bset:
.                break
.        else:
.            if aset:
.                aset.add(b)
.            elif bset:
.                bset.add(a)
.            else:
.                ret.append(sets.Set([a,b]))
.            continue
.        if aset is not bset:
.            ret.remove(aset)
.            ret.remove(bset)
.            ret.append(aset.union(bset))
.
.    return [list(s) for s in ret]
.                
.print merge(input)
More information about the Python-list mailing list