home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9465 < prev    next >
Encoding:
Internet Message Format  |  1992-07-23  |  2.1 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!tulane!uflorida!mailer.cc.fsu.edu!fsu1.cc.fsu.edu!rose
  2. From: rose@fsu1.cc.fsu.edu (Kermit Rose)
  3. Newsgroups: sci.math
  4. Subject: Re: ? Quick algorithm for random covering sets ?
  5. Message-ID: <1992Jul18.233109.4713@mailer.cc.fsu.edu>
  6. Date: 23 Jul 92 18:01:41 GMT
  7. References: <SQUASH.92Jul17215435@bourbaki.msri.org> <1992Jul18.131603.26814@mailer.cc.fsu.edu>
  8. Reply-To: rose@fsu1.cc.fsu.edu
  9. Organization: Florida State University
  10. Lines: 28
  11. News-Software: VAX/VMS VNEWS 1.3-4
  12.  
  13. In article <1992Jul18.131603.26814@mailer.cc.fsu.edu>, rose@fsu1.cc.fsu.edu (Kermit Rose) writes...
  14. >In article <SQUASH.92Jul17215435@bourbaki.msri.org>, squash@bourbaki.msri.org (Jonathan King) writes...
  15. >>Do any of you have a suggestion for a "fast" algorithm which:
  16. >>   Given positive integers D > K > 2, the algorithm hands me K "random"
  17. >>non-empty subsets of {1,...,D} whose union is all of {1,...,D} and with no
  18. >>element common to all K sets.
  19. >> 
  20. >>"Fast" doesn't have a technical definition here, -the algorithm needs to go
  21. >>inside a deeply nested loop.  "Random" isn't precise either but at least the
  22. >>probability that element d is in set S_k should be close to independent of d.
  23. >> 
  24. >>I'm looking for a easily-programmable, practical algorithm, even if it has
  25. >>theoretical shortcomings.        -Jonathan,  squash@math.ufl.edu
  26. > 
  27. > Here is a FAST algorithm.  Use a random number generator which returns an 
  28. integer in the range {1,2,....K} each time it is called.  Then for j = 
  29. 1,2,3,.....D, call this random number generator to give the number s_j.  
  30. Put j in subset number s_j.
  31.  
  32. It is possible that we could make your program run MUCH faster by figuring 
  33. out how to make it unnecessary to have this random generation withing the 
  34. deeply nested loop.  Is the problem too complicated to post or describe in 
  35. e-mail.  Perhaps I or someone can suggest alternative ways to see the 
  36. problem that will take less calculation.
  37. > 
  38. >rose@fsu1.cc.fsu.edu          To be sure I see your response, use e-mail.
  39. -----------------------------------------------------------------------
  40. Be of good cheer, for it is much more fun than being depressed.
  41.