[NBLUG/talk] Request for help--how to program shuffling

[Eric Eisenhart]

On Wed, May 21, 2003 at 10:15:09PM -0700, Steve Zimmerman wrote:
> Let's say we have a computer with internal state
> capable of representing 52! (fifty-two factorial).
> 
> Then let's say we have a file with all 52! possible 
> combinations of a regular deck of cards,
> each one on a line by itself (total 52! newlines in
> file).

I want that hard drive.

I'm willing to share with all of you.

If there's sufficient bandwidth, I'm willing to share with the planet. 
Other planets, even.

(That's roughly an order of magnitude of orders of magnitude beyond the
current total digital storage capacity of the human race.  6.7 * 10^43
yottabytes if you use one byte for each combination)

> Now let's say we have a program capable of randomly
> selecting one of the 52! lines in the file.
> 
> There's our random shuffle, correct?

Well...  there's 2 (at least)problems:
1) Only if you can randomly pick from any of the 52! lines with an equal
probability of any given line being picked.  With a little quick math I find
that ln(52!)/ln(2) == 225.58(...).  So, picking randomly would take, say,
226 coin tosses, except that the most significant bit would bias the
selection, so you'd have to have 225 coin tosses and one weighted-random
choice (2^225/52!=~.67; roughly 2/3rds weighted towards 0 instead of 1)

2) As far as CPU time goes, you've just traded in a hard problem (randomly
picking from 52! choices) that can be broken into components (say, 51
individual random choices) into an even harder problem (randomly picking
from 52! choices and then finding your choice)

> So there's a computer that can beat Kasparov,
> but there's not a computer that can perform
> a random shuffle of 52 elements???

Chess is complex but relatively deterministic.  Randomness requires a lack
of determinism.  If there's no extra help, then a computer is incapable of
true randomness; all operations will always provide the same result given
the same set of starting circumstances.  Various methodologies have been
used to simulate randomness fairly well.  Some computers have randomness
generators built in (my old Commodore-64 did!) and these days there are
sources of relatively random data (network, keyboard and mouse interrupt
timings) that can be collected to provide even better randomness.

Besides, shuffling isn't as good as you might think.  If you try, then a
card on top will remain on top forever.  (with extreme skill you can even
shuffle a deck right back into the starting state, but IIRC, it takes quite
a few shuffles) With normal, imperfect, human shuffling (where the
interleaving is randomly ~1-4 cards on each side) with a perfect-condition
deck (no bias towards specific cards) this effect is minimized but still
present.

Ever play Solitaire and win?  It's difficult to shuffle a deck sufficiently
afterwards.  4 perfect shuffles and dealing to 4 people and they each have a
suit.  4 imperfect shuffles and dealing to 4 people and they're each very
long in one suit; makes for a terrible game of Bridge, Hearts or Spades.
-- 
Eric Eisenhart
NBLUG Co-Founder & Vice-President Pro Tempore
The North Bay Linux Users Group
http://nblug.org/
eric at nblug.org, IRC: Freiheit at freenode, AIM: falschfreiheit, ICQ: 48217244
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://nblug.org/pipermail/talk/attachments/20030522/24469052/attachment.pgp