home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / theory / 2932 < prev    next >
Encoding:
Internet Message Format  |  1993-01-27  |  2.4 KB
  1. Xref: sparky comp.theory:2932 sci.crypt:7159 rec.puzzles:8569
  2. Path: sparky!uunet!mcsun!sunic!ericom!exucom.exu.ericsson.se!texsun!cronkite.Central.Sun.COM!news2me.EBay.Sun.COM!sun-barr!cs.utexas.edu!zaphod.mps.ohio-state.edu!howland.reston.ans.net!spool.mu.edu!yale.edu!cs.yale.edu!ginkgo.theory.cs.yale.edu!fischer
  3. From: fischer-michael@cs.yale.edu (Michael Fischer)
  4. Newsgroups: comp.theory,sci.crypt,rec.puzzles
  5. Subject: Re: Generating a Random Permutation
  6. Message-ID: <1993Jan26.170151.9146@cs.yale.edu>
  7. Date: 26 Jan 93 17:01:51 GMT
  8. References: <C1FpMw.4Ip@ccu.umanitoba.ca>
  9. Sender: news@cs.yale.edu (Usenet News)
  10. Reply-To: fischer-michael@cs.yale.edu (Michael Fischer)
  11. Followup-To: comp.theory,sci.crypt,rec.puzzles
  12. Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
  13. Lines: 36
  14. Nntp-Posting-Host: ginkgo.theory.cs.yale.edu
  15. X-Newsreader: TIN [version 1.1az (for az) PL8]
  16.  
  17. Stephen Bloch (sbloch@silver.cs.umanitoba.ca) wrote:
  18. : sumner@math.scarolina.edu (David Sumner) writes:
  19. : >> In an earlier post I wrote that an easy way to generate a
  20. : >> random permutation of the integers 1-n was:
  21. : >> >      ++++++++++++++
  22. : >> >  Initialize  A[n] as the array [1, 2, 3, 4,..., n]
  23. : >> >        for i=1 to n
  24. : >> >        z = random(n)
  25. : >> >        t = a[i]
  26. : >> >        a[i] = a[z]
  27. : >> >        a[z] = t
  28. : >> >        next i
  29. : >> >    ++++++++++++++
  30. : >> There is a typo in this. The line 'z = random(n)' should
  31. : >> be 'z = random(i)'
  32.  
  33. : I THINK (but am not sure) the
  34. : corrected one is also incorrect, for the reasons Thomas states.
  35.  
  36. The corrected algorithm can be seen to be correct by a simple
  37. inductive argument.  Namely, after the i-th iteration, A[1]...A[i]
  38. contains a random permutation of 1,...,i, and A[i+1]...A[n] contains
  39. the numbers (i+1),...,n in sequence.  The next iteration swaps A[i+1]
  40. = (i+1) with a randomly-chosen A[z], where 1 <= z <= i+1.  Thus, (i+1)
  41. is equally likely to go into any of the first i+1 slots, and the
  42. remaining positions end up being filled with a random permutation of
  43. 1,...,i.  This results in a random permutation of 1,...,i+1 as
  44. desired.
  45.  
  46. Since the induction hypothesis is obviously true for i=0, it holds for
  47. all i<=n by induction.  Thus, after the last iteration, A[1],...,A[n]
  48. contains a random permutation of 1,...,n.
  49.  
  50. ==================================================
  51. | Michael Fischer <fischer-michael@cs.yale.edu>  |
  52. ==================================================
  53.