exercise: partition a list by equivalence

[John Machin]

Reinhold Birkenfeld wrote:
> 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

FWIW, here's a brief UAT report:

Appears to work: Reinhold, David, Xah (v2)
Has bug(s): John L (v*), Brian (v*)
Incomprehensible: Xah (v*)

'Come back after lunch' award goes to Xah v2, which at a glance appears
to be O(N**4) -- dictionary.update() inside 3-deep nest of 'for'
statements.

Here's a small input that busts all non-working versions:

input: [[1, 2], [3, 4], [2, 3], [4, 5]]
merge_RB  -> [[1, 2, 3, 4, 5]]
merge_DE  -> [[1, 2, 3, 4, 5]]
merge_JL  -> [[1, 2, 3, 4], [5]]
merge_JL2 -> [[1, 2, 3, 4], [5]]
merge_BB  -> []
merge_XL  -> [[1, 2, 3, 4, 5], [3, 4, 5]]
merge_XL2 -> [[1, 2, 3, 4, 5]]