[R] repeat until function
Prof Brian Ripley
ripley at stats.ox.ac.uk
Wed Nov 12 18:45:09 CET 2003
On Wed, 12 Nov 2003, Liaw, Andy wrote:
> As others already pointed out, the fast way is to use sample().
>
> What I'd like to add is the following, which I learned from peeking at the C
> code underneath sample(): To draw n samples without replacement from 1:N
> (N>=n), you only need a loop from 1 to n that used up n random numbers. The
> algorithm is simple, but IMHO very clever:
>
> pop <- 1:N
> samp <- rep(NA, n)
> soFar <- N
> for (i in 1:n) {
> idx <- ceiling(runif(1) * soFar)
> samp[i] <- pop[idx]
> ## swap the soFar-th and idx-th element of pop.
> tmp <- pop[soFar]
> pop[soFar] <- pop[idx]
> pop[idx] <- tmp
> ## decrease the population by 1.
> soFar <- soFar - 1
> }
>
> This is obviously not efficient in high-level languages like R, but in terms
> of algorithm, it is a lot more efficient than check-and-reject. IMHO this
> should be described in some book, but I have not seen any book describing
> it.
Ripley (1987) Stochastic Simulation, pp.80-1 for one. I am pretty sure it
is Knuth's book, although I don't have that to hand. I attribute it to
Moses & Oakford (1963).
--
Brian D. Ripley, ripley at stats.ox.ac.uk
Professor of Applied Statistics, http://www.stats.ox.ac.uk/~ripley/
University of Oxford, Tel: +44 1865 272861 (self)
1 South Parks Road, +44 1865 272866 (PA)
Oxford OX1 3TG, UK Fax: +44 1865 272595
More information about the R-help
mailing list