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 ahopk...@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
> 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 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.
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.
m...@alcyone.com (Erik Max Francis) wrote in <3985C75F.7030A...@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.
> 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>.
> 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.
Jake Speed wrote: > 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.
|
