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('qwertyuio p')

def pileshuffle(DEC K, 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]

Re: shuffling elements of a list

On 30 May 2006 20:18:19 -0700, greenflame <alikakakhel@ya hoo.com> wrote:[color=blue]
> 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.[/color]

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

[greenflame]

Re: shuffling elements of a list

Zhang Fan wrote:[color=blue]
> On 30 May 2006 20:18:19 -0700, greenflame <alikakakhel@ya hoo.com> wrote:[color=green]
> > 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.[/color]
>
> The random module has a `shuffle' method. It "Shuffle the sequence x
> in place".
> It may be help for you[/color]

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]

Re: shuffling elements of a list

"greenflame " <alikakakhel@ya hoo.com> writes:
[color=blue]
> 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.[/color]

Sounds like a job for (ta-da-daa) DSU[0].

That said, here are some comments on your implementation.
[color=blue]
> ----------
> testdeck = list('qwertyuio p')
>
> def pileshuffle(DEC K, NUMPILES):[/color]

Ouch. Why use uppercase for the parameter names? This implies either
shouting, or constants, neither of which is appropriate.
[color=blue]
> """Split the deck given into NUMPILES piles. Then also put the
> piles""" \
> """ together to make the deck again."""[/color]

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(dec k, numpiles):
""" Split the deck bla bla bla
bla bla bla. """
[color=blue]
> # Define a list of lists which is the piles
> PILES = [[]] * NUMPILES[/color]

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(li st())

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)]
[color=blue]
> card = 0
> pilenum = 0
> while card < len(DECK):
> PILES[pilenum].append(DECK[card])
> card += 1
> if pilenum < NUMPILES:
> pilenum += 1
> else:
> pilenum = 0[/color]

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::
[color=blue][color=green][color=darkred]
>>> def pileshuffle(dec k, numpiles):[/color][/color][/color]
... """ 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
...[color=blue][color=green][color=darkred]
>>> deck = list("qwertyuio p")
>>> print pileshuffle(dec k, 5)[/color][/color][/color]
[['q', 'y'], ['w', 'u'], ['e', 'i'], ['r', 'o'], ['t', 'p']][color=blue][color=green][color=darkred]
>>> print pileshuffle(dec k, 3)[/color][/color][/color]
[['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.or g/wiki/Schwartzian_Tra nsform>

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

[John Machin]

Re: shuffling elements of a list

On 31/05/2006 1:18 PM, greenflame wrote:[color=blue]
> 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.
>[/color]

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(de ck, 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(de ck, 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('q wertyuiop', 3, True)
pileshuffle2('q wertyuiop', 3)
pileshuffle1('q wertyuiop', 3, False)

[Scott David Daniels]

Re: shuffling elements of a list

greenflame wrote:[color=blue]
> Zhang Fan wrote:[color=green]
>> ... The random module has a `shuffle' method. It "Shuffle the sequence x
>> in place". It may be help for you[/color]
>
> 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.[/color]

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
scott.daniels@a cm.org

[greenflame]

Re: shuffling elements of a list

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]

Re: shuffling elements of a list

On 30 May 2006 21:53:32 -0700, "greenflame " <alikakakhel@ya hoo.com>
wrote:
[color=blue]
>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.[/color]

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 lexicographical ly,
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(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

..)

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

David C. Ullrich

[SuperHik]

Re: shuffling elements of a list

greenflame wrote:[color=blue]
> Zhang Fan wrote:[color=green]
>> On 30 May 2006 20:18:19 -0700, greenflame <alikakakhel@ya hoo.com> wrote:[color=darkred]
>>> 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.[/color]
>> The random module has a `shuffle' method. It "Shuffle the sequence x
>> in place".
>> It may be help for you[/color]
>
> 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.
>[/color]
You should update your Python then ;)
It's a very nice method:
[color=blue][color=green][color=darkred]
>>> import random
>>> random.seed()
>>>
>>> list = [1,21,23,4,5]
>>> random.shuffle( list)
>>> print list[/color][/color][/color]
[5, 4, 23, 1, 21]

[Sybren Stuvel]

Re: shuffling elements of a list

David C Ullrich enlightened us with:[color=blue]
> 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.[/color]

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]

Re: shuffling elements of a list

On Wed, 31 May 2006 12:17:11 +0200, Sybren Stuvel
<sybrenUSE@YOUR thirdtower.com. imagination> wrote:
[color=blue]
>David C Ullrich enlightened us with:[color=green]
>> 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.[/color]
>
>This is often done in database queries that need to randomize the data
>;-)[/color]

Huh. Gotta find a good patent attorney<g>.
[color=blue]
>Sybren[/color]


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

David C. Ullrich

[Roger Miller]

Re: shuffling elements of a list

Sybren Stuvel wrote:[color=blue]
> David C Ullrich enlightened us with:[color=green]
> > 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.[/color]
>
> 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[/color]

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]

Re: shuffling elements of a list

Roger Miller wrote:
[color=blue]
> 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.

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

</F>

[Gerard Flanagan]

Re: shuffling elements of a list

Ben Finney wrote:
[snip][color=blue]
>
> 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
>[/color]

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]

Re: shuffling elements of a list

Gerard Flanagan wrote:
[color=blue]
> Ben Finney wrote:[/color]
[color=blue][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]

No need to maintain an index ;-)

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

Assuming deck is a list, that is.

Peter