home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2838 < prev    next >
Encoding:
Internet Message Format  |  1993-01-08  |  1.4 KB
  1. Xref: sparky comp.theory:2838 sci.crypt:6559 sci.math:17868 rec.puzzles:8296
  2. Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
  3. Path: sparky!uunet!zaphod.mps.ohio-state.edu!uwm.edu!wupost!gumby!destroyer!cs.ubc.ca!uw-beaver!newsfeed.rice.edu!rice!news.rice.edu!dougm
  4. From: dougm@titan.cs.rice.edu (Doug Moore)
  5. Subject: Re: Looking for random permutation generation algorithms
  6. In-Reply-To: karr@cs.cornell.edu's message of Fri, 8 Jan 1993 17:28:24 GMT
  7. Message-ID: <DOUGM.93Jan8161707@titan.cs.rice.edu>
  8. Sender: news@rice.edu (News)
  9. Organization: Rice University Computer Science, Houston, Texas
  10. References: <1993Jan7.165939.11149@cs.cornell.edu> <2607@usna.NAVY.MIL>
  11.     <1993Jan8.163909.20820@cs.cornell.edu>
  12.     <1993Jan8.172824.22910@cs.cornell.edu>
  13. Date: Fri, 8 Jan 1993 22:17:07 GMT
  14. Lines: 14
  15.  
  16. Now that the problem of computing a 1-1 mapping from the integers 0 <=
  17. i < n! to permuatations of n elements has been solved, can anyone
  18. suggest a way to compute a function f(i,j), 0 <= i < n!, 0 <= j < n,
  19. such that f(i,j) is the jth component of the ith permutation IN
  20. CONSTANT SPACE?  Personally, I can't.  Maybe it's impossible.
  21.  
  22. An application?  Suppose you wanted to implement a truly uniform
  23. open-addressed hashing scheme.  The algorithms proposed so far will
  24. generate a permutation (probe sequence) from a key, but require linear
  25. additional space to do it.  That would not be acceptible for a large
  26. hash table.  Any ideas?
  27.  
  28. Doug Moore
  29. (dougm@cs.rice.edu)
  30.