From clarkem@unpsun1.cc.unp.ac.za Wed Mar 30 15:18:55 EST 1994 Article: 12424 of comp.lang.lisp Xref: glinda.oz.cs.cmu.edu comp.ai:21424 comp.lang.lisp:12424 sci.math:68463 Path: honeydew.srv.cs.cmu.edu!nntp.club.cc.cmu.edu!news.mic.ucla.edu!library.ucla.edu!agate!howland.reston.ans.net!ee.und.ac.za!tplinfm From: Matthew C. Clarke Newsgroups: rec.puzzles,comp.ai,comp.lang.lisp,sci.math Subject: SUMMARY: card shuffling algorithms Date: 30 Mar 1994 10:05:06 GMT Organization: University of Natal, Pietermaritzburg Lines: 173 Distribution: world Message-ID: <2nbisi$37l@lucy.ee.und.ac.za> NNTP-Posting-Host: mac.cs.unp.ac.za X-UserAgent: Version 1.1.3 X-XXMessage-ID: X-XXDate: Wed, 30 Mar 94 10:16:06 GMT 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 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 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 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 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 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 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 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: tnaidoo@unpcs1.cs.unp.ac.za