home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9440 < prev    next >
Encoding:
Internet Message Format  |  1992-07-22  |  1.8 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!caen!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.131603.26814@mailer.cc.fsu.edu>
  6. Date: 23 Jul 92 05:13:39 GMT
  7. References: <SQUASH.92Jul17215435@bourbaki.msri.org>
  8. Reply-To: rose@fsu1.cc.fsu.edu
  9. Organization: Florida State University
  10. Lines: 27
  11. News-Software: VAX/VMS VNEWS 1.3-4
  12.  
  13. In article <SQUASH.92Jul17215435@bourbaki.msri.org>, squash@bourbaki.msri.org (Jonathan King) writes...
  14. >Do any of you have a suggestion for a "fast" algorithm which:
  15. >   Given positive integers D > K > 2, the algorithm hands me K "random"
  16. >non-empty subsets of {1,...,D} whose union is all of {1,...,D} and with no
  17. >element common to all K sets.
  18. > 
  19. >"Fast" doesn't have a technical definition here, -the algorithm needs to go
  20. >inside a deeply nested loop.  "Random" isn't precise either but at least the
  21. >probability that element d is in set S_k should be close to independent of d.
  22. > 
  23. >I'm looking for a easily-programmable, practical algorithm, even if it has
  24. >theoretical shortcomings.        -Jonathan,  squash@math.ufl.edu
  25.  
  26. There should be real numbers b_1,b_2,...b_K with the property that
  27. the sequences 
  28. {[b_1],[2 b_1],[3 b_1],....}
  29. {[b_2],[2 b_2],[3 b_2],...}
  30. ..    
  31. {[b_K],[2 b_K],[3 b_K],...}  have pairwise null intersection.
  32.    [x] means largest integer less than or equal to x.
  33.  
  34. I do not remember how to find these numbers.  The value of D is not 
  35. relevant since the b's are the same for all D. 
  36.  
  37. rose@fsu1.cc.fsu.edu          To be sure I see your response, use e-mail.
  38. -----------------------------------------------------------------------
  39. Be of good cheer, for it is much more fun than being depressed.
  40.