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
Re: generating random permutations on the fly
Posted: Sep 15, 2006 5:33 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


Robert Israel wrote:

> You probably don't really want to generate such a huge permutation.

In fact, in the context of Monte Carlo simulation, n is generally a
comfortable upper bound of what is really needed as a number of
simulation, but it is not always the case, even for n as large as 10^9.

> The question is what you'd want to do with it. You can probably get
> by with just generating the part of it that you really need.


Exactly. The problem is that I don't know in advance what will be this
part.

> If all you're going to look at is where 1..p have been
> transported, you can just generate a random one-to-one mapping f from
> 1..p into 1..n. Something like this:
>
> for i from 1 to p do
> repeat
> x := random number in 1..n
> until x has not already been taken;
> f(i):= x;
>
> To check whether x has already been taken, without the expense of an
> array of n bits, you might construct a heap or a hash table.


Nice idea. It should work pretty well as far as p < sqrt(n). After that
point, most of the x will be rejected, thus I will spend a lot of time
generating random numbers for nothing.

> If p is known in advance, I suspect a hash table might be the best choice.

p is not known in advance, but nevertheless I will give your idea a
try!

Thanks a lot for this useful suggestion.

Régis 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.