home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / theory / 2944 < prev    next >
Encoding:
Internet Message Format  |  1993-01-29  |  1.7 KB
  1. Xref: sparky comp.theory:2944 sci.crypt:7202 rec.puzzles:8647
  2. Newsgroups: comp.theory,sci.crypt,rec.puzzles
  3. Path: sparky!uunet!spool.mu.edu!agate!ames!pacbell.com!att-out!walter!homebrew!jgn
  4. From: jgn@homebrew.bellcore.com (Joseph G. Niederberger)
  5. Subject: Re: Generating a Random Permutation
  6. Message-ID: <1993Jan28.214325.17733@walter.bellcore.com>
  7. Sender: news@walter.bellcore.com
  8. Nntp-Posting-Host: homebrew.bellcore.com
  9. Reply-To: jgn@homebrew.UUCP (Joseph G. Niederberger)
  10. Organization: Bellcore, Morristown, NJ
  11. References: <sumner.727366153@milo.math.scarolina.edu> <4fKlI4200WB8Aps_9A@andrew.cmu.edu> <C1FpMw.4Ip@ccu.umanitoba.ca>
  12. Date: Thu, 28 Jan 93 21:43:25 GMT
  13. Lines: 30
  14.  
  15. In article <C1FpMw.4Ip@ccu.umanitoba.ca> sbloch@silver.cs.umanitoba.ca (Stephen Bloch) writes:
  16. >sumner@math.scarolina.edu (David Sumner) writes:
  17. >>> In an earlier post I wrote that an easy way to generate a
  18. >>> random permutation of the integers 1-n was:
  19. >>> >      ++++++++++++++
  20. >>> >  Initialize  A[n] as the array [1, 2, 3, 4,..., n]
  21. >>> >        for i=1 to n
  22. >>> >        z = random(n)
  23. >>> >        t = a[i]
  24. >>> >        a[i] = a[z]
  25. >>> >        a[z] = t
  26. >>> >        next i
  27. >>> >    ++++++++++++++
  28. >>> There is a typo in this. The line 'z = random(n)' should
  29. >>> be 'z = random(i)'
  30. >
  31. >and "Thomas W. Strong, Jr." <strong+@CMU.EDU> replies:
  32. >>I have to agree with the algorithm as originally presented.  What it
  33. >>effectively does is it takes each item and puts it in a random position.
  34. >><stuff deleted>
  35.  
  36. >No, the original algorithm is incorrect (for the simple combinatorial
  37. >reason several people have posted).  
  38.  
  39. This is counterintuitive to a degree that it reminds me of the famous
  40. "Monte Hall" flap of a couple years back.  There must be some way to
  41. make money from this... ;^)
  42.  
  43. Joe N.
  44.  
  45.