Re: Looking for random permutation generation algorithms

Article View: comp.theory

Article #1922

#1922

From: Doug Moore
Date: Fri, 08 Jan 1993 22:17

14 lines
1409 bytes

Now that the problem of computing a 1-1 mapping from the integers 0 <=
i < n! to permuatations of n elements has been solved, can anyone
suggest a way to compute a function f(i,j), 0 <= i < n!, 0 <= j < n,
such that f(i,j) is the jth component of the ith permutation IN
CONSTANT SPACE?  Personally, I can't.  Maybe it's impossible.

An application?  Suppose you wanted to implement a truly uniform
open-addressed hashing scheme.  The algorithms proposed so far will
generate a permutation (probe sequence) from a key, but require linear
additional space to do it.  That would not be acceptible for a large
hash table.  Any ideas?

Doug Moore
(dougm@cs.rice.edu)

Technical Details

Message-ID: <DOUGM.93Jan8161707@titan.cs.rice.edu>

Path:

arc1-ca.pugleaf.net!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

References:

<1993Jan7.165939.11149@cs.cornell.edu> <2607@usna.NAVY.MIL> <1993Jan8.163909.20820@cs.cornell.edu> <1993Jan8.172824.22910@cs.cornell.edu>

Show Full Headers

Complete Article Headers

Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
Path: arc1-ca.pugleaf.net!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
From: dougm@titan.cs.rice.edu (Doug Moore)
Subject: Re: Looking for random permutation generation algorithms
In-Reply-To: karr@cs.cornell.edu's message of Fri, 8 Jan 1993 17:28:24 GMT
Message-ID: <DOUGM.93Jan8161707@titan.cs.rice.edu>
Sender: news@rice.edu (News)
Organization: Rice University Computer Science, Houston, Texas
References: <1993Jan7.165939.11149@cs.cornell.edu> <2607@usna.NAVY.MIL>
 <1993Jan8.163909.20820@cs.cornell.edu>
 <1993Jan8.172824.22910@cs.cornell.edu>
Date: Fri, 8 Jan 1993 22:17:07 GMT
Lines: 14

Reply to Parent Message