**To**:**fwp@technofile.org****Subject**:**[FWP] Shufflebug****From**:**Amir Karger <karger@fermi2.chem.yale.edu>**- Date: Tue, 18 Jul 2000 12:07:58 -0400
- Cc: karger@post.harvard.edu, jwjr@ignition.name.net

Hi. Last year, I mentioned my "Random Schwartz" card shuffle on fwp: @{$deck->{"cards"}} = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [$_, rand] } @{$deck->{"cards"}}; http://bumppo.net/lists/fun-with-perl/1999/08/msg00029.html http://bumppo.net/lists/fun-with-perl/1999/08/msg00076.html start two of the threads. Folks seemed to agree it was pretty random, although Chip turner said (in msg00044.html) "I'm not 100% convinced this is a truly random sort, but I think it should be pretty good. Hopefully the rand perl uses (which I hope desperately isn't the default rand that the OS comes with, but deep down I suspect it is) is decent enough to give a good distribution." Well, today I got mail from James Wetterau, suggesting that it's not. (Minor snippage) ----- Forwarded message from James Wetterau <jwjr@ignition.name.net> ----- Subject: bug in Games-Cards-1.45 I believe your shuffle has a bug (at least if it's meant to produce a truly shuffled deck). Your shuffle revolves around the ordering of (up to about) 52 consecutive calls to rand. On a machine with 15 randbits I believe the randomization sequence repeats within 2 ^ 32 iterations. (According to my Solaris manpage.) This means that there are only 2 ^ 32 unique deck combinations that can be created out of these calls by pulling out a set of 52 consecutive random calls from the sequence. Assuming this ratio, holds constant, even a machine with 31 randbits would repeat its sequence of numbers after 2^64 iterations. (I'm guessing at this.) Now the total number of deck combinations possible by shuffling a true deck is between 2 ^ 225 and 2 ^ 226. So if you only shuffle once, you're playing with a greatly diminished subset of the possible truly well-shuffled decks. Now then, a good solution might be to shuffle multiple times. I haven't thought this through, but possibly application of a random number of shuffles, say between 5 and 10 times, might allow your shuffles to get to all the decks in the possible space of shuffled decks. But users should definitely not rely on single calls to shuffle from a pristine ordering to offer them a truly random, well-shuffled deck, because they'll only get one from among a very small subset of possible deck permutations. ----- End forwarded message ----- I know nothing about randomness. So the questions: (1) do you agree that this problem exists? (2) do you agree with the fix? It seems clear that always doing 5 shuffles gives you exactly the same number of permutations as doing 1 shuffle. However, I can't work out whether randomly doing between 5 & 10 random shuffles would multiply the number of possible decks by 6 (10-5+1), or give you much more randomness. Would it help if I chose a random number of random numbers in between the shuffles, thereby shifting the randomization sequence? This doesn't seem to matter terribly much, since 2^32 hands is still more than you could ever play in your lifetime. But fwp isn't necessarily about things that matter, right? <plug> For those who might care, the Games::Cards module which includes this shuffle just had a new release, v1.45, which includes two perl/Tk solitaire games. That's *definitely* fun with perl! </plug> -Amir Karger karger@fermi2.chem.yale.edu ==== Want to unsubscribe from Fun With Perl? Well, if you insist... ==== Send email to <fwp-request@technofile.org> with message _body_ ==== unsubscribe

**Follow-Ups**:**free card URLs Re: [FWP] Shufflebug***From:*"David L. Nicol" <david@kasey.umkc.edu>

**Re: [FWP] Shufflebug***From:*Jeff Pinyan <jeffp@crusoe.net>

**Re: [FWP] Shufflebug***From:*Ira Joseph Woodhead <ira@av.com>

**Re: [FWP] Shufflebug***From:*merlyn@stonehenge.com (Randal L. Schwartz)

- Prev by Date:
**[FWP] ANNC: Perl Golf Apocalypse** - Next by Date:
**Re: [FWP] Shufflebug** - Prev by thread:
**Re: [FWP] fun with numbers** - Next by thread:
**Re: [FWP] Shufflebug** - Navigation:
**Date Index | Thread Index | Search | Other lists at bumppo.net**