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

[Reinhold Birkenfeld]

Xah Lee wrote:
> here's the answer to the partition by equivalence exercise.

Your Python solution is, as expected, wrong (try with
[[10, 8], [7, 3], [1, 7], [5, 4], [2, 2], [3, 8], [7, 10], [2, 3], [6,
10], [3, 2]]
for example).

The solution by John Lenton is wrong, too.

The solution by Brian Beck delivers the correct result for most input,
but for some input lists like
[[3, 3], [8, 7], [3, 2], [8, 5], [5, 6], [6, 3], [10, 8], [8, 10], [4,
10], [10, 2]]
it chokes and returns the empty list.

My solution (which may not be the fastest or most effective, but till
now is the shortest <wink> and it works):

def merge(pairings):
    sets = {}
    for x1, x2 in pairings:
        newset = (sets.get(x1, frozenset([x1]))
                  | sets.get(x2, frozenset([x2])))
        for i in newset:
            sets[i] = newset

    return [list(aset) for aset in set(sets.itervalues())]


Reinhold