exercise: partition a list by equivalence

[John Lenton]

On Fri, Feb 18, 2005 at 03:21:10PM -0800, John Machin wrote:
> Not robust in the face of input like:
> [[1,1]]
> or
> [[1,2], [1,2]]
> or
> [[1,2], [2,1]]
> or
> [[1,2], [2,3], [3,1]]

oops, my bad.

> 
> needs "if first == second: continue" here
> 
> >             if has_first and has_second:
> 
> needs "if rev[first] == rev[second]: continue" here

an 'is' is enough, and better.

> >                 rev[first].extend(rev[second])
> >                 rev[second][:] = []
> >                 rev[second] = rev[first]
> >             elif has_first:
> >                 rev[first].append(second)
> >                 rev[second] = rev[first]
> >             elif has_second:
> >                 rev[second].append(first)
> >                 rev[first] = rev[second]
> >             else:
> >                 copy = [first, second]
> >                 res.append(copy)
> 
> My reaction to the "magic" by which res grows was "omigod that's the
> most horrible thing I've seen for quite a while" but there was worse to
> come :-)

what is magic about it? is it really that horrible?

> List appending is O(1) only in the amortised sense. Extending is not
> O(1) in any sense. Neither is the list comparison that is necessary for
> robustness (using your data structure, that is).
> 
> You don't need to think. This problem has been extensively picked over
> by folk who are a lot smarter than us, starting from 30 years ago.
> Google for "disjoint set" and "union-find". One gets the impression
> that the best possible algorithm would be slightly *worse* than O(n).

Of course! I'd forgotten clean about union-find. And yes, it's
O(n*log(n)) union and find, and my implementation is O(n**2) for
union, O(1) for find; I'm pleased that, in spite of having forgotten
about union-find, I "reinvented" (heh) something that is better than
the "naive" implementation we saw in class.

Now I'm even more worried about your dismissal of this as magic and
horrible.

-- 
John Lenton (john at grulic.org.ar) -- Random fortune:
Why don't you fix your little problem... and light this candle?
		-- Alan Shepherd, the first man into space, Gemini program
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 196 bytes
Desc: Digital signature
URL: <http://mail.python.org/pipermail/python-list/attachments/20050218/095baccc/attachment.sig>