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

