The Math Forum

Search All of the Math Forum:

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

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

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


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


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

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.