shuffling elements of a list

[David C. Ullrich]

Man, an error made _six years ago_ and people are still bringing it up ...

Sorry. Happens to me on sci.math all the time. The point really
wasn't that you were so dumb, the point was just the opposite.
(_I_ didb't bring it up, btw - I would never have known about
it if FL hadn't pointed it out.)


************************

David C. Ullrich

 

[Iain King]

On 30 May 2006 21:53:32 -0700, "greenflame" <[email protected]>
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

 

[Peter Otten]

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])]

sorted() and list.sort() will happily accept a key function argument and
then do the decorating/undecorating for you:
.... return sorted(items, key=key)
....[6, 5, 3, 4, 8, 9, 0, 7, 1, 2]

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

Turning the key() function into a lambda is left as an exercise

Peter