Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.num-analysis.independent

Topic: generating random permutations on the fly
Replies: 6   Last Post: Sep 18, 2006 9:56 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
regis lebrun

Posts: 6
Registered: 9/14/06
generating random permutations on the fly
Posted: Sep 14, 2006 6:25 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Hi,

Trying to implement the Latin Hypercube Sampling algorithm, I am
interrested in an algorithm able to generate a random permutation
uniformly distributed among the n! possible permutations of [1, ...,
n]. Such an algorithm is well-known (see Donald E. Knuth, `The Art of
Computer Programming: Sorting and Searching' (Vol 3, 3rd Ed, 1997),
Addison-Wesley, ISBN 0201896850) and is widely available in open source
packages, but I can't use it if I want to generate a really huge
permutation (let's say n=10^9).
In fact, I am looking for an algorithm able to tell me where a given i
in [1,...,n] has been transported by the permmutation, for i=1..p in
this order, with p << n (hopefuly), that has a memory cost much lesser
than n (in the worst case, or in the mean case).

Any reference/algorithm/source code/theory would be GREATLY
appreciated!

Regis LEBRUN




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.