[R] repeat until function

[Prof Brian Ripley]

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