home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2848 < prev    next >
Encoding:
Text File  |  1993-01-09  |  2.4 KB  |  46 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  3. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  4. Subject: Re: Looking for random permutation generation algorithms
  5. Message-ID: <1993Jan9.234606.12595@CSD-NewsHost.Stanford.EDU>
  6. Sender: news@CSD-NewsHost.Stanford.EDU
  7. Organization: Computer Science Department,  Stanford University.
  8. References: <1993Jan6.014749.15323@ee.ubc.ca> <1993Jan8.210013.24614@CSD-NewsHost.Stanford.EDU> <24824@galaxy.ucr.edu>
  9. Date: Sat, 9 Jan 1993 23:46:06 GMT
  10. Lines: 34
  11.  
  12. In article <24824@galaxy.ucr.edu> marek@wigry.ucr.edu (marek chrobak) writes:
  13. >In article <1993Jan8.210013.24614@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
  14. >>But for N >> M it has two drawbacks: the time to initialize the array,
  15. >>and the space required for it, both being O(N).  In contrast Floyd's
  16. >>method requires space O(M) and time somewhere between O(M) and O(M^2)
  17. >>depending on the method used to test for repetitions.  (For N some
  18. >>modest multiple of M one might instead keep track of repetitions using
  19. >>an array of N bits, i.e. N/8 bytes, initialized to 0.)
  20. >
  21. >This method also can be implemented in O(M) space and O(M logM) time.
  22. >
  23. >The general idea is that there is no need to initialize and maintain
  24. >the whole array. Only M entries can be changed, so for other entries
  25. >A[i] = i. Use any balanced search tree for storing needed information.
  26. >For details see: Chrobak, Harter, A note on random sampling, Information
  27. >Processing Letters 29 (1988) 255-256.
  28.  
  29. Quite right, I'd entirely forgotten that option was available.  It
  30. dates back at least to the 70's though it would take me a while to dig
  31. up an instance.
  32.  
  33. This rather undermines the rationale Bentley offered for Floyd's
  34. algorithm, at least for permutations, where I don't right now see any
  35. big advantage of either algorithm over the other.  Simulating A[i]=i
  36. with any prescribed amount of time and storage is essentially identical
  37. in difficulty to inserting a default output ahead of K in Floyd's
  38. algorithm under the same prescription.
  39.  
  40. The interest in Floyd's algorithm (besides its ingenuity) therefore
  41. would seem to be its greater applicability, namely to the problem of
  42. sampling combinations.  Here the storage requirement is only N bits,
  43. which for N < M log_2 M would seem close to unbeatable.
  44. -- 
  45. Vaughan Pratt                There's safety in certain numbers.
  46.