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