Some time ago my supervisor asked on my behalf if anyone could provide
code
for shuffling a deck of cards. Our thanks to the many people who replied.
Here is a summary of the replies....
* Many people suggested Knuth's Algorithm from his book "The Art of
Computer
Programming"
* Another algorithm, suggested by many was...
Number each card from 1 to 52
Repeatedly generate a random number between 1..52
(discarding any number generated previously)
This new sequence = order of cards after being shuffled
* John Krueger <·······@samwise.cs.hope.edu> sugested, in addition to
Knuth's
Algorithm, a method of emulating a kind of shuffle that is usually done
on a
pack of cards.
Randomly cut the deck near the middle
Combine by picking one of the top two cards at random and placing
it
onto the out pile.
Repeat this about three or four times.
* Ken Johnson <···@festival.edinburgh.ac.uk> suggested the following
algorithm
Uniquely represent each card [e.g. card(1,h) or card(1,d)]
Assign a random number to each card
Keysort that list and your cards are shuffled.
If you are dealing with cards that are replaced instead of being dealt
to
exhaustion, or with drawing a single card from a pack and replacing it
before
drawing the next, there is a simplier way.
Generate a random integer from 1..13 and another from 1..4 to determine
the
suit.
* Scott D. Anderson <········@titanic.cs.umass.edu> suggested two
algorithms
The first is based on the idea that you uniquely number all of the n!
permutations of the cards, and that numbering is invertible. Then to
find
a perfect shuffle, you randomly generate a number between 0 and n!-1
and
return that permutation of cards.
The next algorithm is based on the idea that if you uniformly and
randomly
insert an element into a perfect shuffle of size k, you get a perfect
shuffle
of size k+1. The algorithm just starts with a perfect shuffle of size
1
which is very trivial, and works up to a desired size.
* Peter Dudey <······@research.cs.orst.edu> suggested the foll. algorithm
Divide the deck into two parts and interleave them
e.g. 1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 0
1 5 2 6 3 7 4 8 9 0
This probaly ought to be done several times.
You could if you liked choose the dividing point according to a
Gaussian
Distribution
* Andrew James Bromage <·······@mundil.cs.mu.OZ.AU> did some analysis on
card shuffling algorithms. He found that the best technique that he
thought
of was a simple interleave. His approaches were statistically inclined.
* Ingemar Hulthage <········@morue.usc.edu> suggested the foll. algorithm
1. Assign each card a random integer from 0 to the largest integer
available
2. Sort the cards using the assigned integer as the key
3. Check if any cards got assigned the same integer, if not go to 5.
4. Reassign integers to cards that did not get a unique integer and
go to 2.
5. Return the sorted cards.
If the range of random integers is large step 4. will almost never be
necessary.
* Balasubramanian Narasimhan <·····@euler.bd.psu.edu> suggested the
following...
> Persi Diaconis is probably the authority on this topic. A popular
>article reported on his analysis of card shuffling, but I forget the
> reference. The main conclusion, if I remember it well, was that
> one need to use at least 7 riffle shuffles.
>
> Here are some references that I found using the Cumulative Index to
> Statistics.
AUTHOR = Dave Bayer
AUTHOR = Persi Diaconis
TITLE = Trailing the dovetail shuffle to its lair
JOURNAL = Ann. of Appl. Probability
VOLUME = 2
PAGES = 294-313
YEAR = 1992
KEYWORDS = Probability; Gambling
AUTHOR = David Aldous
AUTHOR = Persi Diaconis
TITLE = Shuffling cards and stopping times
JOURNAL = Amer. Math'l. Monthly
VOLUME = 93
PAGES = 333-348
YEAR = 1986
KEYWORDS = Random walk
AUTHOR = Simo Puntanen
TITLE = Shuffling cards
JOURNAL = Teaching Stat.
VOLUME = 13
PAGES = 28-31
YEAR = 1991
KEYWORDS = Computing
AUTHOR = L. Flatto
AUTHOR = A. M. Odlyzko
AUTHOR = D. B. Wales
TITLE = Random shuffles and group representations
JOURNAL = Ann. of Probability
VOLUME = 13
PAGES = 154-178
YEAR = 1985
AUTHOR = John W. Rosenthal
TITLE = Card Shuffling
JOURNAL = Math. Magazine
VOLUME = 54
PAGES = 64-67
YEAR = 1981
AUTHOR = Edward O. Thorp
TITLE = Nonrandom shuffling with applications to the game of Faro
JOURNAL = J. of the Amer. Stat'l. Assn.
VOLUME = 68
PAGES = 842-847
YEAR = 1973
KEYWORDS = Gambling; Blackjack
AUTHOR = Gary Gottlieb
TITLE = Non-random shuffling for multiple decks
JOURNAL = J. of Appl. Probab.
VOLUME = 24
PAGES = 402-410
YEAR = 1987
KEYWORDS = Brownian bridge; Gambling
AUTHOR = Steve Medvedoff
AUTHOR = Kent Morrison
TITLE = Groups of perfect shuffles
JOURNAL = Math. Magazine
VOLUME = 60
PAGES = 3-14
YEAR = 1987
KEYWORDS = Games
AUTHOR = P. Glaister
TITLE = Card shuffling -- A micro computer approach
JOURNAL = Math. and Computer Educ., The MATYC J., Inc.
VOLUME = 24
PAGES = 7-10
YEAR = 1990
KEYWORDS = Teaching
--
Throshni Naidoo
Dept. of Computer Science
University of Natal, Pietermaritzburg
e-mail: ·······@unpcs1.cs.unp.ac.za
I missed the question. :-(
Do you want just a shuffle, or a derangement on a 52-set?
--
Jered Floyd
·······@vela.acs.oakland.edu
GAT d? -p+ c++++ l+ u++ ··@ m++ s/-- n--- h++ f? g- w++ t+++ r++
PGP Public key available by finger."
In article <··········@lucy.ee.und.ac.za> Matthew C. Clarke,
·······@unpsun1.cc.unp.ac.za writes:
>* Peter Dudey <······@research.cs.orst.edu> suggested the foll. algorithm
> Divide the deck into two parts and interleave them
> e.g. 1 2 3 4 5 6 7 8 9 0
> 1 2 3 4 5 6 7 8 9 0
> 1 5 2 6 3 7 4 8 9 0
> This probaly ought to be done several times.
Try this (several times). You will find that it returns to its original
order after three shuffles. Note that 1, 8, 9 and 0 remain in the same
place and that 2 -> 5 -> 3 -> 2 and 4 -> 6 -> 7 -> 4.
These deterministic shuffles always cycle (after so many shuffles) and
are no use for doing 'real' shuffles, unless some variation is built in
at each stage. Even then I wouldn't like to have to analyse them. I
wouldn't think each permutation was equaly likely unless some very
careful analysis was done.
Hi,
I needed to write a card shuffling algorithm a while ago, and wrote a short
C program (based on Knuth's algorithm) to take care of it. The main shuffle
routine is very straightforward, viz.
--------------------
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 */
}
}
--------------------
I wrote this as part of a project on Bridge - my dealer generates random
deals (approx 1000/s) and stores them in a binary file using just 13 bytes
for each full deck - a separate program can then expand these into full
bridge deals. If anyone wants the source code, LMK.
Cheers,
vaughan
--
\_ \_ \_\_ \_ \_ \_\_\_ \_ \_ \_\_ \_\_ \_vaughan marks\_
\_ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_
\_ \_ \_\_\_ \_ \_ \_ \_ \_\_\_ \_\_\_ \_ \_ ········@cs.man.ac.uk
\_\_ \_ \_ \_\_\_ \_\_\_ \_ \_ \_ \_ \_ \_