Newsgroups: rec.puzzles
From: hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: Fri, 8 Apr 1994 00:07:43 GMT
Subject: Re: SUMMARY: card shuffling algorithms

vaugh...@cs.man.ac.uk (Vaughan Marks) offers the following card
shuffling algorithm:

> Card deck[52];                             /* the deck of cards */

> void shuffle()
> /* shuffle a deck of cards using random() */
> {
>Card tmp, left=51, n;

>   while (left) {
>     n=random() % left;                     /* pick a rand card */
>     tmp=deck[left];
>     deck[left--]=deck[n];                  /* move the chosen card */
>     deck[n]=tmp;                           /* pick from those remaining */
>   }
> }

m...@hubcap.clemson.edu (Matthew Saltzman) makes the small point that
"n=random() % left" may be badly distributed if random() misbehaves.
But there's a much more certain bug: the line in question should be
"n=random() % (left+1)" or some other method of producing a random
integer in {0,...,left}.  As written, the program will not generate
uniformly distributed shuffles.  For instance, every permutation will
be even, and the original last card will _never_ end up in last place.
I'm amused by this bug, since I suspect it results from "repairing" a
non-bug: the correct algorithm sometimes exchanges a card with itself.
I wonder if there is any quantitative way of comparing the
nonuniformity caused by this bug with the nonuniformity caused by the
FCB* of using n=random()%52.

jo...@rogue.Princeton.EDU (Joel Evan Rosenberg) notes that Vaughan is
storing a bridge deal in 13 bytes, while the information should be
compressible into 12 bytes. [ 2^96 > C(52,13).C(39,13).C(26,13), where
C(n,k) denotes the binomial coefficient n!/(k!(n-k)!). ]  But how,
Joel asks, can this be done so that the cards in each hand can be
determined quickly?  If we can perform 96-bit arithmetic sufficiently
quickly, this boils down to finding a bijective mapping from
{0,..,C(n,k)} to the set of k-element subsets of {0,...,n-1}.
This can be done as follows.

Given as input integers 0<=k<=n and N in {0,..,C(n,k)},
 1. If k is zero, stop.
 2. If N>=C(n-1,k), output n-1, decrease N by C(n-1,k), and decrement k.
    In this case, N will now be in {0,...,C(n-1,k-1)}.
 3. Decrease n by 1 and go back to step 1.

This will output the set in decreasing order.

Now given an integer NN representing a bridge deal, first form a
vector deck[52] containing the cards and set top=51.  We will run the
above algorithm once for each the first three players.  When the above
algorithm outputs a number t, we will deal deck[t] to the designated
player and set deck[t]=deck[top--].  Then to deal the hand,

  1. Run the above algorithm with N=NN%C(52,13), n=52, and k=13,
     dealing cards to the first player.
  2. Set NN=Floor(NN/C(52,13)).
  3. Run the algorithm with N=NN%C(39,13), n=39, and k=13, dealing
     cards to the second player.
  4. Run the algorithm with N=Floor(NN/C(39,13)), n=26, and k=13,
     dealing cards to the third player.
  5. Give all the remaining cards to the fourth player.

The only drawback of this method is that the cards are not dealt in a
useful order.  It should be possible to deal them in order, at the
expense of an increase in bookkeeping and a greater use of
high-precision arithmetic.

Dan Hoey -- Hoey@AIC.NRL.Navy.Mil -- * FCB = Frequently Committed Bug