Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 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

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

Date Subject Author
9/14/06 regis lebrun
9/14/06 Han de Bruijn
9/14/06 regis lebrun
9/14/06 Robert Israel
9/15/06 regis lebrun
9/15/06 Herman Rubin
9/18/06 regis lebrun