[R] repeat until function

[Liaw, Andy]

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.

Just my $0.02...
Andy

> -----Original Message-----
> From: Ragnhild Sørum [mailto:rsoerum80 at hotmail.com] 
> Sent: Wednesday, November 12, 2003 9:26 AM
> To: r-help at stat.math.ethz.ch
> Subject: [R] repeat until function
> 
> 
> Hi,
> 
> I'm in this situation:
> I what to generate N random numbers(integer) that are 
> different from each 
> other.
> One suggestion:
> 
> tabel <- rep(NULL, N)
> for (i in 1:N){
>    temp <- as.integer(runif(1,1,max))
>    if(temp in tabel) {
>        repeat (?) (temp <- as.integer(runif(i,i,max)))
>        until (?) ((temp in tabel) ==FALSE)
>    }
>    else{ tabel[i] <- temp}
> 
> I can't use repeat/until - don't exist....
> Any suggestions?
> 
> 
> Thanks
> *Ragnhild*
> 
> _________________________________________________________________
> MSN Messenger http://www.msn.no/messenger Den korteste veien 
> mellom deg og 
> dine venner
> 
> ______________________________________________
> R-help at stat.math.ethz.ch mailing list 
> https://www.stat.math.ethz.ch/mailman/listinfo> /r-help
>