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]]
--
http://mail.python.org/mailman/listinfo/python-list
