Random permutation of arrays

Statement of the problem

Our purpose is to

The algorithm

PERMUTE(A)
------------
n = length(A)
for (i = 1, ..., n) {
    SWAP(A, i, RANDOM(i, n))
}

Implementation

The following is an R implementation of this algorithm.

random <- function(a, b)
{
    a + floor(runif(1) * (b-a+1))
}

permute <- function(x)
{
    n <- length(x)
    for (i in seq_along(x))
    {
        s <- random(i, n)
        x[c(i, s)] <- x[c(s, i)]
    }
    x
}

One example of runtime:

system.time(permute(1:1000000))
##    user  system elapsed 
##   5.224   0.000   5.221
system.time(sample(1:1000000))
##    user  system elapsed 
##   0.040   0.000   0.036

Run time as function of sample size:

etime <- function(n)
{
    system.time(permute(1:n))["elapsed"]
}
N <- seq(1000, 100000, 5000)
T <- sapply(N, etime)
plot(N, T)
plot of chunk unnamed-chunk-3

plot of chunk unnamed-chunk-3