home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2846 < prev    next >
Encoding:
Internet Message Format  |  1993-01-09  |  2.2 KB
  1. Xref: sparky comp.theory:2846 sci.crypt:6583 sci.math:17897 rec.puzzles:8302
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!rutgers!network.ucsd.edu!galaxy!wigry!marek
  3. From: marek@wigry.ucr.edu (marek chrobak)
  4. Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
  5. Subject: Re: Looking for random permutation generation algorithms
  6. Message-ID: <24824@galaxy.ucr.edu>
  7. Date: 9 Jan 93 21:09:50 GMT
  8. References: <1993Jan6.014749.15323@ee.ubc.ca> <1993Jan8.210013.24614@CSD-NewsHost.Stanford.EDU>
  9. Sender: news@galaxy.ucr.edu
  10. Followup-To: comp.theory
  11. Organization: University of California, Riverside
  12. Lines: 33
  13. Nntp-Posting-Host: wigry.ucr.edu
  14.  
  15. In article <1993Jan8.210013.24614@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
  16.  
  17. >As noted in Bentley's December 1987 column, an alternative to Floyd's
  18. >algorithm is to initialize an array a[1..N] to a[i]=i and then scan
  19. >along from a[1] to a[M], exchanging each such a[i] with a randomly
  20. >selected a[j] for j >= i.
  21. >
  22. >For N = M (Woo's question) this method is the one Jim Roth gave.  It is
  23. >preferable to Floyd's method because it does not entail testing for
  24. >previous occurrences.
  25. >
  26. >But for N >> M it has two drawbacks: the time to initialize the array,
  27. >and the space required for it, both being O(N).  In contrast Floyd's
  28. >method requires space O(M) and time somewhere between O(M) and O(M^2)
  29. >depending on the method used to test for repetitions.  (For N some
  30. >modest multiple of M one might instead keep track of repetitions using
  31. >an array of N bits, i.e. N/8 bytes, initialized to 0.)
  32.  
  33. This method also can be implemented in O(M) space and O(M logM) time.
  34.  
  35. The general idea is that there is no need to initialize and maintain
  36. the whole array. Only M entries can be changed, so for other entries
  37. A[i] = i. Use any balanced search tree for storing needed information.
  38. For details see: Chrobak, Harter, A note on random sampling, Information
  39. Processing Letters 29 (1988) 255-256.
  40.  
  41. Marek
  42.  
  43. -- 
  44. ------------------------------------------------------------------
  45. Marek Chrobak                              email: marek@cs.ucr.edu
  46. Department of Computer Science             phone: (714) 787-3769
  47. University of California, Riverside        fax  : (714) 787-4643
  48.