home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / programm / 2615 < prev    next >
Encoding:
Internet Message Format  |  1992-09-15  |  2.2 KB
  1. Xref: sparky comp.programming:2615 comp.theory:1928 sci.math.num-analysis:2732
  2. Path: sparky!uunet!olivea!spool.mu.edu!darwin.sura.net!haven.umd.edu!mimsy!cvl!zogwarg!hoey
  3. From: hoey@zogwarg.etl.army.mil (Dan Hoey)
  4. Newsgroups: comp.programming,comp.theory,sci.math.num-analysis
  5. Subject: Re: Proving fair shuffles (was: FULL HOUSE)
  6. Message-ID: <1152@zogwarg.etl.army.mil>
  7. Date: 15 Sep 92 17:33:21 GMT
  8. References: <schnitzi.716563018@eola.cs.ucf.edu> <1992Sep13.223147.28768@wuecl.wustl.edu> <LOWRY.92Sep14133846@rotor.watson.ibm.com> <prn5c10@fido.asd.sgi.com> <1992Sep14.184939.10440@austin.eds.com> <dak.716561621@messua>
  9. Followup-To: comp.programming
  10. Organization: Naval Research Laboratory, Washington, DC
  11. Lines: 47
  12.  
  13. schnitzi@cs.ucf.edu (Mark Schnitzius) writes:
  14.  
  15. >Assuming you have a true random number generator, is there
  16. >a way to _prove_ that a particular algorithm performs an
  17. >honest shuffle (i.e. each card has equal possibility of 
  18. >being in each place)?  Are there any order(n) shuffling
  19. >routines?
  20.  
  21. Yes, and yes, and the algorithm's in Knuth, and it's faqfully posted
  22. here and there (it was in comp.sources.d less than a month ago)
  23. possibly because it's a frequently assigned homework exercise.  But
  24. that still doesn't prevent mtj@babar.asd.sgi.com (Michael Jones) from
  25. posting the egregious pseudo-shuffle
  26.  
  27. bad> for (card = 0; card < 52; card++)
  28. bad>    {
  29. bad>    swap = random() % 52;
  30. bad>    temp = deck[card];
  31. bad>           deck[card] = deck[swap];
  32. bad>                        deck[swap] = temp;
  33. bad>    }
  34.  
  35. or yenne@austin.eds.com (Britt Yenne) from misshuffling the first five
  36. cards with lossage like
  37.  
  38. bad>    for(i = 0; i < 5; i++)
  39. bad>    {
  40. bad>        n = random() % 52;
  41. bad>        s = card[n];
  42. bad>        card[n] = card[i];
  43. bad>        card[i] = s;
  44. bad>    }
  45.  
  46. Even dak@messua.informatik.rwth-aachen.de (David Kastrup), offering
  47. the good advice to
  48.  
  49. > Use rand/(MAXUNSIGNED/52 + 1) instead of rand%52.
  50.  
  51. doesn't mention that always folding rand to a 52-element range is the
  52. commonest, most obvious sign of an incompetent shuffler.
  53.  
  54. But, you may notice, I have not provided a corrected shuffling
  55. algorithm!  Think of it as an incentive to go read Knuth, or a Pons
  56. Asinorum for the lazy student.
  57.  
  58. Dan Hoey
  59. Hoey@AIC.NRL.Navy.Mil
  60.