random.shuffle?
Albert Hopkins
I wrote a script on my RedHat Linux 6.2 box at home and was pleasantly
surprised to see that there was a random.shuffle function. However,
when I later ran the script on my RedHat 6.2 box at work, there was
no such function. Anyone have any idea where it came from?
--
Albert Hopkins
Sr. Systems Specialist
Dynacare Laboratories
ahop...@dynacare.com
I've found that things like "If you change even one configuration setting and
your system ceases to function, or functions in a manner other than expected,
our support staff will laugh at you in the sinister manner of Joseph Stalin
just before he enslaved eastern Europe" helps to draw peoples attention to
essential details like this.
-Edward Grimm
François Pinard
> I wrote a script on my RedHat Linux 6.2 box at home and was pleasantly
> surprised to see that there was a random.shuffle function. However,
> when I later ran the script on my RedHat 6.2 box at work, there was
> no such function. Anyone have any idea where it came from?
No, but it is easily rewritten. Let's see... (untested)
import whrandom
def shuffle(items):
"""Shuffle ITEMS in place. ITEMS should normally be a list."""
for top in range(len(items)-1, 0, -1):
index = whrandom.randint(0, top)
items[index], items[top] = items[top], items[index]
--
François Pinard http://www.iro.umontreal.ca/~pinard
Erik Max Francis
> def shuffle(items):
> """Shuffle ITEMS in place. ITEMS should normally be a list."""
> for top in range(len(items)-1, 0, -1):
> index = whrandom.randint(0, top)
> items[index], items[top] = items[top], items[index]
This is a biased shuffling algorithm. When swapping cards, you'd want
to pick the other card from the whole of the deck, not the deck that
you've touched so far. If you start with a sorted deck, for instance,
it's easy to see that cards can't end up in every place; see Knuth.
Better would be this:
def shuffle(list):
count = len(list)
for i in range(count):
j = whrandom.randint(count)
list[i], list[j] = list[j], list[i]
Simpler, too.
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
/ \ Love is the most subtle form of self-interest.
\__/ Holbrook Jackson
Fat Boy and Little Man / http://www.fatboyandlittleman.com/
Watch Fat Boy and Little Man go about their antics.
Jake Speed
<3985C75F...@alcyone.com>:
>François Pinard wrote:
>
>> def shuffle(items):
>> """Shuffle ITEMS in place. ITEMS should normally be a list."""
>> for top in range(len(items)-1, 0, -1):
>> index = whrandom.randint(0, top)
>> items[index], items[top] = items[top], items[index]
>
>This is a biased shuffling algorithm. When swapping cards, you'd want
>to pick the other card from the whole of the deck, not the deck that
>you've touched so far. If you start with a sorted deck, for instance,
>it's easy to see that cards can't end up in every place; see Knuth.
It's not selecting from the deck touched so far; it's
selecting from the untouched deck -- it's counting backwards.
This is the correct way to do it.
-Speed!
Tim Peters
> ...
> Better would be this:
>
> def shuffle(list):
> count = len(list)
> for i in range(count):
> j = whrandom.randint(count)
> list[i], list[j] = list[j], list[i]
>
> Simpler, too.
Actually, random.shuffle was added to Python to stop that bad algorithm from
propagating! *That's* the biased one. The easiest way to see that it must
be biased is that there are count**count possible outcomes (you pick one of
count values for j on each of count iterations), and count! does not divide
count**count for count > 2: some permutations are thus necessarily more
likely than others, provided the list has at least 3 elements.
Note that there are count! possible outcomes in François's paraphrase of the
std Python random.shuffle. That doesn't mean it's unbiased, but does mean
that it's at worst not so *obviously* biased <wink>.
Exhaustive discussion can be found via DejaNews.
François Pinard
> François Pinard wrote:
> > def shuffle(items):
> > """Shuffle ITEMS in place. ITEMS should normally be a list."""
> > for top in range(len(items)-1, 0, -1):
> > index = whrandom.randint(0, top)
> > items[index], items[top] = items[top], items[index]
> This is a biased shuffling algorithm. When swapping cards, you'd want
> to pick the other card from the whole of the deck, not the deck that
> you've touched so far. If you start with a sorted deck, for instance,
> it's easy to see that cards can't end up in every place; see Knuth.
"See Knuth" is rather vague. It reads like "Go fishing!". It would be
more polite giving some precise reference of what you want me to look at.
You also write: "It's easy to see that cards can't end up in every place;".
I may be stubborn and opaque, but I do not see it. Please kindly explain.
My feeling is that the algorithm above corresponds to what is being written
in the Art of Computer Programming, volume II, section 3.4.2, algorithm P.
My transcription may be wrong, of course, but then, please tell me where.
Erik Max Francis
> It's not selecting from the deck touched so far; it's
> selecting from the untouched deck -- it's counting backwards.
> This is the correct way to do it.
Indeed. I managed to rather egregiously remember the Knuth algorithm
exactly wrong. How embarassing.
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
/ \ Love is like war: easy to begin but very hard to stop.
\__/ H.L. Mencken
7 sisters productions / http://www.7sisters.com/
Web design for the future.