shuffling elements of a list

[Roger Miller]

Sybren Stuvel wrote:
> David C  Ullrich enlightened us with:
> > I thought that the fact that you could use the same trick for
> > _shuffling_ a list was my idea, gonna make me rich and famous. I
> > guess I'm not the only one who thought of it. Anyway, you can use
> > DSU to _shuffle_ a list by decorating the list with random numbers.
>
> This is often done in database queries that need to randomize the data
> ;-)
>
> Sybren
> --
> The problem with the world is stupidity. Not saying there should be a
> capital punishment for stupidity, but why don't we just take the
> safety labels off of everything and let the problem solve itself?
>                                              Frank Zappa

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]