home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / programm / 2614 < prev    next >
Encoding:
Text File  |  1992-09-15  |  2.0 KB  |  60 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!spool.mu.edu!news.nd.edu!mentor.cc.purdue.edu!news
  3. From: ags@seaman.cc.purdue.edu (Dave Seaman)
  4. Subject: Re: Proving fair shuffles (was: FULL HOUSE)
  5. Message-ID: <BuMtr1.6vC@mentor.cc.purdue.edu>
  6. Sender: news@mentor.cc.purdue.edu (USENET News)
  7. Organization: Purdue University
  8. References: <psqghc8@fido.asd.sgi.com>
  9. Distribution: comp
  10. Date: Tue, 15 Sep 1992 18:23:24 GMT
  11. Lines: 47
  12.  
  13. In article <psqghc8@fido.asd.sgi.com> mtj@babar.asd.sgi.com (Michael  
  14. Jones) writes:
  15. [Re: honest shuffle]
  16. > Certainly such an algorithm exists, and is O(n):
  17.  
  18. >    while (old not empty)
  19. >        begin
  20. >        select a card in old at random
  21. >        remove card from old
  22. >        add card to new (anywhere: front, back, ...)
  23. >        end
  24.  
  25. This works if you consistently add the card at the front, or consistently  
  26. at the back.
  27.  
  28. > a more common sequence is the one
  29. > in my posted solution:
  30. > 
  31. >     old: array of 52 cards in any order
  32.  
  33. >     for (i = 0; i < 52; i++)
  34. >        swap card[i] and card[random() % 52];
  35.  
  36. This is incorrect. The algorithm generates 52^52 possible sequences of  
  37. random numbers, each equally likely. Different transposition sequences may  
  38. lead to the same final arrangement, but the problem is that 52! (the  
  39. number of possible permutations) does not divide 52^52 (the number of  
  40. transposition sequences that may be generated), thus guaranteeing that the  
  41. permutations are not equally likely.
  42.  
  43. A correct algorithm is
  44.  
  45.     for (i = 51; i > 0; i--)
  46.         swap card[i] and card[random() % (i+1)]
  47.  
  48. The fact that I have written the loop to execute for decreasing i is a  
  49. minor point that makes the notation simpler. The major difference is the  
  50. presence of "random() % (i+1)" instead of "random() % 52" in the swap.
  51.  
  52. This algorithm generates exactly 52! possible sequences of transpositions,  
  53. all equally likely. Each possible permutation corresponds to exactly one  
  54. such sequence of transpositions. Therefore the result is an honest shuffle  
  55. (if the random number generator is good).
  56.  
  57. --
  58. Dave Seaman
  59. ags@seaman.cc.purdue.edu
  60.