shuffling elements of a list

[David C. Ullrich]

On Wed, 31 May 2006 23:05:14 +0200, Fredrik Lundh
<fredrik at pythonware.com> 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