shuffling elements of a list

[Ben Finney]

Re: shuffling elements of a list

"Gerard Flanagan" <grflanagan@yah oo.co.uk> writes:
[color=blue]
> Ben Finney wrote:[color=green]
> > pile_index = 0
> > for card in deck:
> > piles[pile_index].append(card)
> > pile_index = (pile_index + 1) % numpiles
> >[/color]
>
> no need to maintain an index ;-)
>
> piles = [ list() for _ in range(n) ]
> for i, card in enumerate(deck) :
> piles[i % numpiles].append(card)[/color]

That's a matter of style. I prefer what I wrote, since I've given an
explicit name to the calculation you're doing inside the [] operator;
that way, anyone reading the code knows *why* the calculation is done
in this particular case.

If, of course, the index was a simple increment-by-one each time, your
'enumerate' usage would be clearer.

--
\ "We spend the first twelve months of our children's lives |
`\ teaching them to walk and talk and the next twelve years |
_o__) telling them to sit down and shut up." -- Phyllis Diller |
Ben Finney

[David C. Ullrich]

Re: shuffling elements of a list

On Wed, 31 May 2006 23:05:14 +0200, Fredrik Lundh
<fredrik@python ware.com> wrote:
[color=blue]
>Roger Miller wrote:
>[color=green]
>> 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][/color]
>
>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.[/color]

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:
[color=blue]
>see e.g. this thread: http://tinyurl.com/ppgzq[/color]

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

[Erik Max Francis]

Re: shuffling elements of a list

David C. Ullrich wrote:
[color=blue]
> Good example, because we know that EMF is not dumb. I've seen
> the same algorithm many times - the best example is ...[/color]

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

--
Erik Max Francis && max@alcyone.com && http://www.alcyone.com/max/
San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
The purpose of man's life is not happiness but worthiness.
-- Felix Adler

[Gerard Flanagan]

Re: shuffling elements of a list

Peter Otten wrote:[color=blue]
> Gerard Flanagan wrote:
>[color=green]
> > Ben Finney wrote:[/color]
>[color=green][color=darkred]
> >> pile_index = 0
> >> for card in deck:
> >> piles[pile_index].append(card)
> >> pile_index = (pile_index + 1) % numpiles
> >>[/color]
> >
> > no need to maintain an index ;-)
> >
> > piles = [ list() for _ in range(n) ]
> > for i, card in enumerate(deck) :
> > piles[i % numpiles].append(card)[/color]
>
> No need to maintain an index ;-)
>
> piles = [deck[start::numpiles] for start in range(numpiles)][/color]

I am humbled :-)

Gerard

[Alex Martelli]

Re: shuffling elements of a list

Peter Otten <__peter__@web. de> wrote:
[color=blue]
> Gerard Flanagan wrote:[color=green]
> > Ben Finney wrote:[/color]
>[color=green][color=darkred]
> >> pile_index = 0
> >> for card in deck:
> >> piles[pile_index].append(card)
> >> pile_index = (pile_index + 1) % numpiles[/color]
> >
> > no need to maintain an index ;-)
> >
> > piles = [ list() for _ in range(n) ]
> > for i, card in enumerate(deck) :
> > piles[i % numpiles].append(card)[/color]
>
> No need to maintain an index ;-)
>
> piles = [deck[start::numpiles] for start in range(numpiles)]
>
> Assuming deck is a list, that is.[/color]

Or, for deck hypothetically being an arbitrary iterable,

import itertools as it
piles = [ list() for _ in range(numpiles) ]
for pile, card in it.izip(it.cycl e(piles), deck):
pile.append(car d)

i.e., let itertools do the cycling for you. But, sure, for this problem
one can no doubt assume that deck is sliceable, and extended slicing
(==slicing with a stride) comes in handy.


Alex

[David C. Ullrich]

Re: shuffling elements of a list

On Thu, 01 Jun 2006 03:25:23 -0700, Erik Max Francis <max@alcyone.co m>
wrote:
[color=blue]
>David C. Ullrich wrote:
>[color=green]
>> Good example, because we know that EMF is not dumb. I've seen
>> the same algorithm many times - the best example is ...[/color]
>
>Man, an error made _six years ago_ and people are still bringing it up ...[/color]

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]

Re: shuffling elements of a list


David C. Ullrich wrote:[color=blue]
> On 30 May 2006 21:53:32 -0700, "greenflame " <alikakakhel@ya hoo.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(1 0))
>
> 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.appen d((random(), x))
> decorated.sort( )
> res = []
> for x in decorated:
> res.append(x[1])
> return res
>
> .)[/color]

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]

Re: shuffling elements of a list

Iain King wrote:
[color=blue]
> 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])][/color]

sorted() and list.sort() will happily accept a key function argument and
then do the decorating/undecorating for you:
[color=blue][color=green][color=darkred]
>>> from random import random
>>> def key(item): return random()[/color][/color][/color]
....[color=blue][color=green][color=darkred]
>>> def shuffled(items) :[/color][/color][/color]
.... return sorted(items, key=key)
....[color=blue][color=green][color=darkred]
>>> shuffled(range( 10))[/color][/color][/color]
[6, 5, 3, 4, 8, 9, 0, 7, 1, 2]
[color=blue]
> or in nicer python, but still when you're mysitified by map and lambda
> (like me):[/color]

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

Peter