|
|
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
|
|
