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

[Paul McGuire]

Please consider my submission also (Python 2.3-compatible).

-- Paul McGuire

.. 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:
.. s1 = None
.. s2 = None
.. for s in ret:
.. if a in s or b in s:
.. if s1 is None:
.. s1 = s
.. else:
.. s2 = s
.. break
.. else:
.. for s in ret:
.. if a in s:
.. s.add(b)
.. break
.. elif b in s:
.. s.add(a)
.. break
.. else:
.. ret.append(sets.Set([a,b]))
.. continue
.. ret.remove(s1)
.. ret.remove(s2)
.. ret.append(s1.union(s2))
..
.. return [list(s) for s in ret]
..
.. print merge(input)

 

[Paul McGuire]

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)