On Wed, 31 May 2006 23:05:14 +0200, Fredrik Lundh <[EMAIL PROTECTED]> wrote:
>Roger Miller wrote: > >> DSU seems like a lot of trouble to go through in order to use an O(n >> log n) sorting algorithm to do what can be done in O(N) with a few >> lines of code. The core code of random.shuffle() shows how easy it is >> to do it right: >> >> for i in reversed(xrange(1, len(x))): >> # pick an element in x[:i+1] with which to exchange x[i] >> j = int(random() * (i+1)) >> x[i], x[j] = x[j], x[i] > >easy to do it right? you know, the main reason for adding shuffle to >the standard library was that its way too easy to get it wrong. Heh. And I thought it was just me. _I_ find it easy to get the "limits" wrong, even though I have the idea of the algorithm perfectly straight. Better yet is the number of times I've seen a simply wrong algorithm posted online: >see e.g. this thread: http://tinyurl.com/ppgzq Good example, because we know that EMF is not dumb. I've seen the same algorithm many times - the best example is http://www.cigital.com/papers/download/developer_gambling.php Some poker site posted the simply-wrong algorithm in an effort to convince people that their decks were properly shuffled! ************************ David C. Ullrich -- http://mail.python.org/mailman/listinfo/python-list