home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / programm / 2613 < prev    next >
Encoding:
Internet Message Format  |  1992-09-15  |  1.7 KB
  1. Xref: sparky comp.programming:2613 comp.theory:1925
  2. Path: sparky!uunet!wupost!psuvax1!rutgers!sgigate!odin!fido!babar.asd.sgi.com!mtj
  3. From: mtj@babar.asd.sgi.com (Michael Jones)
  4. Newsgroups: comp.programming,comp.theory
  5. Subject: Re: Proving fair shuffles (was: FULL HOUSE)
  6. Message-ID: <psqghc8@fido.asd.sgi.com>
  7. Date: 15 Sep 92 16:21:53 GMT
  8. References: <schnitzi.716563018@eola.cs.ucf.edu>
  9. Sender: news@fido.asd.sgi.com (Usenet News Admin)
  10. Distribution: comp
  11. Organization: Silicon Graphics, Inc.
  12. Lines: 39
  13.  
  14. In article <...>, schnitzi@cs.ucf.edu (Mark Schnitzius) writes:
  15. |> I've been wondering...
  16. |> 
  17. |> Assuming you have a true random number generator, is there
  18. |> a way to _prove_ that a particular algorithm performs an
  19. |> honest shuuffle (i.e. each card has equal possibility of 
  20. |> being in each place)?  Are there any order(n) shuffling
  21. |> routines?
  22. |> 
  23. |> Mark Schnitzius
  24. |> schnitzi@eola.cs.ucf.edu
  25. |> University of Central Florida
  26.  
  27. Certainly such an algorithm exists, and is O(n):
  28.  
  29.    old: array of cards in some order {such as a new deck}
  30.    new: empty array
  31.  
  32.    while (old not empty)
  33.        begin
  34.        select a card in old at random
  35.        remove card from old
  36.        add card to new (anywhere: front, back, ...)
  37.        end
  38.  
  39. This will do just what you ask. Since "remove a card" and
  40. "select a card" are messy for arrays (requires moving
  41. cards down after removal, multiple random probes, or the
  42. advance-and-skip loop) a more common sequence is the one
  43. in my posted solution:
  44.  
  45.     old: array of 52 cards in any order
  46.  
  47.     for (i = 0; i < 52; i++)
  48.        swap card[i] and card[random() % 52];
  49.  
  50. -- Michael Jones    mtj@sgi.com  415.390.1455  M/S 7L-590
  51.             Silicon Graphics, Advanced Graphics Division
  52.             2011 N. Shoreline Blvd., Mtn. View, CA 94039-7311
  53.