What is wrong with this card shuffling algorithm, and how can a bridge deal be stored in 12 bytes so that...
probability/card/shuffling.algorithm New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
What is wrong with this card shuffling algorithm, and how can a bridge
deal be stored in 12 bytes so that the cards in each hand can be
determined quickly?
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 */
}
}
-- Vaughan Marks <vaughanm@cs.man.ac.uk>, April 1994
[ Editor: problem statement reconstructed from Dan Hoey's reply in the
thread "SUMMARY: card shuffling algorithms"; the program is Marks's. ]
Show solution
mjs@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.
[ Editor: as written the loop makes 51 exchanges of two different
cards, so every permutation it produces is odd, not even. ]
joelr@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>, April 1994
* FCB = Frequently Committed Bug