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]

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]

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]

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.

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::
... """ 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>

 

[John Machin]

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]

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
(e-mail address removed)

 

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

 

[SuperHik]

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

 

[David C. Ullrich]

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

 

[David C. Ullrich]

David C Ullrich enlightened us with:

This is often done in database queries that need to randomize the data
;-)

Sybren

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

David C. Ullrich

 

[Roger Miller]

David C Ullrich enlightened us with:

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
j = int(random() * (i+1))
x, x[j] = x[j], x

 

[Fredrik Lundh]

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
j = int(random() * (i+1))
x, x[j] = x[j], x

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

 

[Ben Finney]

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.

 

[Peter Otten]

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

 

[David C. Ullrich]

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
j = int(random() * (i+1))
x, x[j] = x[j], x

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

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 ...

 

[Gerard Flanagan]

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]

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