Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: generating random permutations on the fly
Posted:
Sep 18, 2006 9:56 AM


Herman Rubin a écrit :
> >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. > > Most of the random numbers will not be rejected until > n/2 have already been obtained. The cost of testing > is likely to be worse after some multiple of sqrt(n), > but not the cost of random numbers. >
You are perfectly right: I made a confusion with the birthday paradox, trying to generate in one run p numbers among n without collision.
> > An alternative method is to find the elements in order. > Let f(k) = \prod_0^{k1} (1  p/(nj)). Then f(k) is > the probability that the first element chosen comes > after k. This can best be done with logarithms and > using approximations and expansions, using exponential > random variables instead of uniform. >
I must confess that I don't see very clearly how to map your suggestion into an algorithm, as I don't know p in advance. Nevertheless, I will try to figure out how to adapt your idea to my problem.
Many thanks for your contribution.
Régis LEBRUN



