shuffling elements of a list

[greenflame]

I would like to make a function that takes a list, more specificaly a
list of strings, and shuffles its elements, like a pile of cards. The
following is a script I tryed to make that implements pile shuffling.

----------
testdeck = list('qwertyuiop')

def pileshuffle(DECK, NUMPILES):
"""Split the deck given into NUMPILES piles. Then also put the
piles""" \
""" together to make the deck again."""

# Define a list of lists which is the piles
PILES = [[]] * NUMPILES

card = 0
pilenum = 0
while card < len(DECK):
PILES[pilenum].append(DECK[card])
card += 1
if pilenum < NUMPILES:
pilenum += 1
else:
pilenum = 0

print PILES
----------

First of all, this script tells me that an index is out of range. I
cannot see why this would be so. Second of all, I would like to have
other methods of shuffling, prefererably riffle shuffling and just
plain randomly arranging the elements of the list.

I very much appreciate any help. Thank you.

[Zhang Fan]

On 30 May 2006 20:18:19 -0700, greenflame <al*********@yahoo.com> wrote:

Second of all, I would like to have
other methods of shuffling, prefererably riffle shuffling and just
plain randomly arranging the elements of the list.

The random module has a `shuffle' method. It "Shuffle the sequence x
in place".
It may be help for you

[greenflame]

Zhang Fan wrote:

On 30 May 2006 20:18:19 -0700, greenflame <al*********@yahoo.com> wrote:

Second of all, I would like to have
other methods of shuffling, prefererably riffle shuffling and just
plain randomly arranging the elements of the list.

The random module has a `shuffle' method. It "Shuffle the sequence x
in place".
It may be help for you

I am sorry but this does not help much. In my version of python (2.3)
this method does not seem to exist. Also from the documentation, it
seems that this method would give a random number.

[Ben Finney]

"greenflame" <al*********@yahoo.com> writes:

I would like to make a function that takes a list, more specificaly a
list of strings, and shuffles its elements, like a pile of cards.
Sounds like a job for (ta-da-daa) DSU[0].

That said, here are some comments on your implementation.
----------
testdeck = list('qwertyuiop')

def pileshuffle(DECK, NUMPILES):
Ouch. Why use uppercase for the parameter names? This implies either
shouting, or constants, neither of which is appropriate.
"""Split the deck given into NUMPILES piles. Then also put the
piles""" \
""" together to make the deck again."""
Remember that triple-quoted strings don't terminate until the next
triple-quote delimiter. This means not having to close and open them
every newline, which is a primary reason to choose them for doc
strings.

def pileshuffle(deck, numpiles):
""" Split the deck bla bla bla
bla bla bla. """
# Define a list of lists which is the piles
PILES = [[]] * NUMPILES
More shouting :-(

That will create a list with many references to the *same* list;
almost certainly not what you want. This creates the desired number of
new lists::

piles = []
for _ in range(numpiles):
piles.append(list())

The '_' name is convention for "We're not going to use this
value".

For something more Pythonic, try a list comprehension::

piles =[list() for _ in range(numpiles)]
card = 0
pilenum = 0
while card < len(DECK):
PILES[pilenum].append(DECK[card])
card += 1
if pilenum < NUMPILES:
pilenum += 1
else:
pilenum = 0

Please don't write C in Python. The 'for' statement allows iteration
directly over a sequence, no need to maintain an index. Also, the
modulus operator is called for with your cycling of the pile index.

pile_index = 0
for card in deck:
piles[pile_index].append(card)
pile_index = (pile_index + 1) % numpiles

Rather than having the function print the result, it should return it;
that way, the caller gets to decide what happens with the result.

return piles

Here's my result with your test input::

def pileshuffle(deck, numpiles): ... """ Split the deck into piles """
... piles =[list() for _ in range(numpiles)]
... pile_index = 0
... for card in deck:
... piles[pile_index].append(card)
... pile_index = (pile_index + 1) % numpiles
... return piles
... deck = list("qwertyuiop")
print pileshuffle(deck, 5) [['q', 'y'], ['w', 'u'], ['e', 'i'], ['r', 'o'], ['t', 'p']] print pileshuffle(deck, 3)

[['q', 'r', 'u', 'p'], ['w', 't', 'i'], ['e', 'y', 'o']]
For actually implementing this, and to allow the flexibility you said
you wanted, using DSU would be most obvious to me.

[0] Decorate-Sort-Undecorate <URL:http://en.wikipedia.org/wiki/Schwartzian_Transform>

--
\ "Pity the meek, for they shall inherit the earth." -- Donald |
`\ Robert Perry Marquis |
_o__) |
Ben Finney

[John Machin]

On 31/05/2006 1:18 PM, greenflame wrote:

I would like to make a function that takes a list, more specificaly a
list of strings, and shuffles its elements, like a pile of cards. The
following is a script I tryed to make that implements pile shuffling.

In general, if you can't see why Python is complaining, insert print
statements.

Anyhow, read the following, run it, read it again, ...

HTH,
John
def pileshuffle1(deck, numpiles, fix1bug=False):
piles = [[]] * numpiles
# 2nd bug: n references to *same* sublist
card = 0
pilenum = 0
while card < len(deck):
print card, pilenum
assert 0 <= pilenum < numpiles
piles[pilenum].append(deck[card])
card += 1
if not fix1bug:
if pilenum < numpiles:
pilenum += 1
else:
pilenum = 0
else:
pilenum = (pilenum + 1) % numpiles
print
print piles

def pileshuffle2(deck, numpiles):
piles = [[] for x in range(numpiles)] # n *different* sublists
for cardindex, card in enumerate(deck):
piles[cardindex % numpiles].append(card)
print
print piles

pileshuffle1('qwertyuiop', 3, True)
pileshuffle2('qwertyuiop', 3)
pileshuffle1('qwertyuiop', 3, False)

[Scott David Daniels]

greenflame wrote:

Zhang Fan wrote:

... The random module has a `shuffle' method. It "Shuffle the sequence x
in place". It may be help for you

I am sorry but this does not help much. In my version of python (2.3)
this method does not seem to exist. Also from the documentation, it
seems that this method would give a random number.

Using Python 2.3.4 on Windows 2000, I get:

import random
lst = range(52)
random.shuffle(lst)
print lst

[8, 26, 9, 10, 22, 39, 36, 48, 29, 5, 50, 16, 15, 2, 40, 33, 3, 7, 37,
43, 11, 0, 30, 49, 32, 44, 24, 47, 42, 27, 23, 28, 12, 18, 13, 35, 1,
34, 25, 45, 21, 20, 46, 38, 17, 31, 6, 4, 14, 41, 51, 19]

Don't be so sure the advice you get is wrong.

--Scott David Daniels
sc***********@acm.org

[greenflame]

Thank you all for all of your help. Also I got the shuffle function to
work. Do not worry I will be back soon with more shuffling! However, I
do not quite understand this DSU that you mention, although it looks
useful.

[David C. Ullrich]

On 30 May 2006 21:53:32 -0700, "greenflame" <al*********@yahoo.com>
wrote:

Thank you all for all of your help. Also I got the shuffle function to
work. Do not worry I will be back soon with more shuffling! However, I
do not quite understand this DSU that you mention, although it looks
useful.

I didn't see any DSU in his post, although I didn't read
it very carefully. DSU is "Decorate Sort Undecorate" -
it's an idiom for efficient sorting. Say you have a list
and you want to sort it using some custom compare function.
That can be very slow. Sorting a list with the builtin
comparison is much faster.

DSU is a trick that lets you use the fast builtin comparison
to sort according to a custom compare. Say you have a list
[x,y,z], these objects have an attribute "a", and you want
to sort on the "a" field. You "decorate" the list,
constructing a new list of tuples

[(x.a, x), (y.a, y), (z.a, z)]

You sort the decorated list using the standard
sort(). Tuples get compared lexicographically,
so this sorts on the "a" field. Then you
"undecorate" the sorted list, stripping
off the first element of each tuple.

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

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

..)

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

David C. Ullrich

[SuperHik]

greenflame wrote:

Zhang Fan wrote:

On 30 May 2006 20:18:19 -0700, greenflame <al*********@yahoo.com> wrote:

Second of all, I would like to have
other methods of shuffling, prefererably riffle shuffling and just
plain randomly arranging the elements of the list.

The random module has a `shuffle' method. It "Shuffle the sequence x
in place".
It may be help for you

I am sorry but this does not help much. In my version of python (2.3)
this method does not seem to exist. Also from the documentation, it
seems that this method would give a random number.

You should update your Python then ;)
It's a very nice method:

import random
random.seed()

list = [1,21,23,4,5]
random.shuffle(list)
print list

[5, 4, 23, 1, 21]

[Sybren Stuvel]

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

[David C. Ullrich]

On Wed, 31 May 2006 12:17:11 +0200, Sybren Stuvel
<sy*******@YOURthirdtower.com.imagination> 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
;-)

Huh. Gotta find a good patent attorney<g>.
Sybren

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

David C. Ullrich

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

[Fredrik Lundh]

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.

see e.g. this thread: http://tinyurl.com/ppgzq

</F>

[Gerard Flanagan]

Ben Finney wrote:
[snip]

Please don't write C in Python. The 'for' statement allows iteration
directly over a sequence, no need to maintain an index. Also, the
modulus operator is called for with your cycling of the pile index.

pile_index = 0
for card in deck:
piles[pile_index].append(card)
pile_index = (pile_index + 1) % numpiles

no need to maintain an index ;-)

piles = [ list() for _ in range(n) ]
for i, card in enumerate(deck):
piles[i % numpiles].append(card)
Gerard

[Peter Otten]

Gerard Flanagan wrote:

Ben Finney wrote:

pile_index = 0
for card in deck:
piles[pile_index].append(card)
pile_index = (pile_index + 1) % numpiles

no need to maintain an index ;-)

piles = [ list() for _ in range(n) ]
for i, card in enumerate(deck):
piles[i % numpiles].append(card)

No need to maintain an index ;-)

piles = [deck[start::numpiles] for start in range(numpiles)]

Assuming deck is a list, that is.

Peter

[Ben Finney]

"Gerard Flanagan" <gr********@yahoo.co.uk> writes:

Ben Finney wrote:

pile_index = 0
for card in deck:
piles[pile_index].append(card)
pile_index = (pile_index + 1) % numpiles

no need to maintain an index ;-)

piles = [ list() for _ in range(n) ]
for i, card in enumerate(deck):
piles[i % numpiles].append(card)

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]

On Wed, 31 May 2006 23:05:14 +0200, Fredrik Lundh
<fr*****@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/downlo...r_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]

David C. Ullrich wrote:

Good example, because we know that EMF is not dumb. I've seen
the same algorithm many times - the best example is ...

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

--
Erik Max Francis && ma*@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]

Peter Otten wrote:

Gerard Flanagan wrote:

Ben Finney wrote:

pile_index = 0
for card in deck:
piles[pile_index].append(card)
pile_index = (pile_index + 1) % numpiles

no need to maintain an index ;-)

piles = [ list() for _ in range(n) ]
for i, card in enumerate(deck):
piles[i % numpiles].append(card)

No need to maintain an index ;-)

piles = [deck[start::numpiles] for start in range(numpiles)]

I am humbled :-)

Gerard

[Alex Martelli]

Peter Otten <__*******@web.de> wrote:

Gerard Flanagan wrote:

Ben Finney wrote:

pile_index = 0
for card in deck:
piles[pile_index].append(card)
pile_index = (pile_index + 1) % numpiles

no need to maintain an index ;-)

piles = [ list() for _ in range(n) ]
for i, card in enumerate(deck):
piles[i % numpiles].append(card)

No need to maintain an index ;-)

piles = [deck[start::numpiles] for start in range(numpiles)]

Assuming deck is a list, that is.

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.cycle(piles), deck):
pile.append(card)

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]

On Thu, 01 Jun 2006 03:25:23 -0700, Erik Max Francis <ma*@alcyone.com>
wrote:

David C. Ullrich wrote:

Good example, because we know that EMF is not dumb. I've seen
the same algorithm many times - the best example is ...

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]

David C. Ullrich wrote:

On 30 May 2006 21:53:32 -0700, "greenflame" <al*********@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

[Peter Otten]

Iain King wrote:

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:

from random import random
def key(item): return random() .... def shuffled(items): .... return sorted(items, key=key)
.... shuffled(range(10))

[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