shuffling elements of a list

[Iain King]

David C. Ullrich wrote:
> On 30 May 2006 21:53:32 -0700, "greenflame" <alikakakhel at yahoo.com>
> wrote:
>
> That's DSU for _sorting_ a list. I read about this, thought
> it was pretty neat. 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.
>
> In fairly old-fashioned Python:
>
> from random import random
>
> def shuffle(data):
>   decorated = map(lambda x: (random(), x), data)
>   decorated.sort()
>   return map(lambda x: x[1], decorated)
>
> print shuffle(range(10))
>
> This prints
>
> [4, 2, 7, 8, 9, 3, 5, 1, 6, 0]
>
> . Seems kinda neat - I have no idea how the efficiency
> compares with the standard sort of "bubble shuffle"
> you were trying to use in your OP, but the point is
> that various off-by-one errors simply don't come up.
>
> (The same thing in extremely awful Python, in case
> you're mystified by map and lambda:
>
> from random import random
>
> def shuffle(data):
>   decorated = []
>   for x in data:
>     decorated.append((random(), x))
>   decorated.sort()
>   res = []
>   for x in decorated:
>     res.append(x[1])
>   return res
>
> .)

or in nicer python, but still when you're mysitified by map and lambda
(like me):

def shuffle(data):
    decorated = [(random(), x) for x in data]
    decorated.sort()
    return [x[1] for x in decorated]

or shorter but possible less readable (and only in 2.4+):

def shuffle(data):
    return [y[1] for y in sorted([(random(), x) for x in data])]

Iain