From: Andrew James BROMAGE
Subject: Re: WANTED: Card shuffling algorithm
Date: 
Message-ID: <9405412.17233@mulga.cs.mu.OZ.AU>
Matthew C. Clarke <·······@unspun1.cc.unp.ac.za> wrote:

>One of my post-grad students is doing a computational analysis of the
>game of Solitaire, and is looking for a good card shuffling algorithm.
>Have any of you got one handy? Lisp code would be good, but other
>languages or just English descriptions would be fine.

I while ago, I did some analysis of card shuffling algorithms. Note that
I was performing a _simulation_, so human error was introduced.

I found the best technique that I thought of was a simple interleave
shuffle. By this I mean you cut the deck into two separate decks. I
cut the deck myself several dozen times and counted the number of
cards in each deck. At the end of this I had a frequency table which
I used to drive a random number generator.

Then the two decks are interleaved. (I took two "ordered" decks and
interleaved them myself so I got another frequency table.) To do this,
you get a certain number of cards from deck 1, then another certain
number from deck 2 and so on until you don't have any more cards left.
These "certain numbers" were obtained from the frequency table. (BTW,
I found that this "certain number" never got more than 4.)

Finally to ensure the end cards would move away from the ends of the
decks, I cut the deck once. (Again using the "cut deck" frequency table
earlier.)

To measure disorder, I counted the number of "reversals", ie if you start
with the numbers [1..52] in the deck, a reversal is a pair of cards in
the shuffled sequence [.. p .. q ..] where p>q. Using this, I found that
as you keep shuffling the reversal count approaches a constant. Using a
threshhold on this number, then, I got a definition of "thoroughly
shuffled". I then started running the card simulation with an unshuffled
deck until the deck was "thoroughly shuffled". Using this technique I
ran about 10000 simulations and in the process discovered how many
shuffles it takes to thoroughly shuffle the deck.  (It ended up at about
9.) For the statistically inclined, the histogram of the number of
shuffles required for a thorough shuffle looked hypergeometric, but I
didn't analyse this further - I'd taken up too much computer time already.

The other thing to note was that I didn't attempt to investigate the
dependence of the number of shuffles required on the frequency tables
which were measured near the start. Perhaps if you are a "better"
shuffler it would take less iterations.

I don't know if that's what you were after, but I found it interesting.

Cheers,
Andrew Bromage
-----------------------------------------------------------------
Andrew Bromage			| "When the going gets weird, the 
				|  weird turn pro." 
·······@mundil.cs.mu.oz.au	|	- Dr Hunter S Thompson 
·······@ecr.mu.oz.au		|   X <- You are here 
If any opinions expressed here match those of the University of
Melbourne, I'll sue them for plagiarism.
From: Earl S. Harris
Subject: Re: WANTED: Card shuffling algorithm
Date: 
Message-ID: <1994Feb23.143918.15049@cs.wm.edu>
  If you want to discuss card shuffling algorithms, you should send E-mail
to Steve Park (····@cs.wm.edu).  He presented an algorithm in a simulation
class which much like the first algorithm presented in this forum.  It was
simple; it used a random number generator, it had a single loop, and the
swap procedure call in the body.  His algorithm was O(n).
  Steve Park was convinced that his algorithm shuffled the cards thoroughly.
And he convinced me.
					Earl Harris Jr.
From: K Johnson
Subject: Re: WANTED: Card shuffling algorithm
Date: 
Message-ID: <CLov3H.K96@festival.ed.ac.uk>
······@ri.cs.wm.edu (Earl S. Harris) writes:

#  If you want to discuss card shuffling algorithms, you should send
#  E-mail to Steve Park (····@cs.wm.edu).... 


Thanks but somebody has now explained the List code to me in a way that
was simple enough for me to understand.  I am satisfied that it works
now. 

Ken "Thick" Johnson


-- 
I'd rather be EATING!                                  # Ken Johnson
                                                       # +44 31 650 3799
This .signature was funded by the Rural .Sig           # Business Studies
Development Fund of the European Community             # Edinburgh University
From: Cyber Surfer
Subject: Re: WANTED: Card shuffling algorithm
Date: 
Message-ID: <CLroFM.Mst@cix.compulink.co.uk>
In article <······················@cs.wm.edu>,
······@ri.cs.wm.edu (Earl S. Harris) writes:
 
>   If you want to discuss card shuffling algorithms, you should send E-mail
> to Steve Park (····@cs.wm.edu).  He presented an algorithm in a simulation
> class which much like the first algorithm presented in this forum.  It was
> simple; it used a random number generator, it had a single loop, and the
> swap procedure call in the body.  His algorithm was O(n).
>   Steve Park was convinced that his algorithm shuffled the cards thoroughly.
> And he convinced me.

Surely you could get by with just random dealing? Pick a card,
and remove it from the "pack". ISTR something like this worked
for me years ago:

I = RND(nCards)
Card = Cards[I]
Cards[I] = Cards[nCards]
Dec(nCards)

Martin Rodgers

--- Cyber Surfing on CIX ---
comp.lang.lisp / 1994 / feb