Generating a Random Permutation in R

Question

I try to implement a example using R in Simulation (2006, 4ed., Elsevier) by Sheldon M. Ross, which wants to generate a random permutation and reads as follows:

Suppose we are interested in generating a permutation of the numbers 1,2,... ,n
which is such that all n! possible orderings are equally likely.
The following algorithm will accomplish this by
- first choosing one of the numbers 1,2,... ,n at random;
- and then putting that number in position n;
- it then chooses at random one of the remaining n-1 numbers and puts that number in position n-1 ;
- it then chooses at random one of the remaining n-2 numbers and puts it in position n-2 ;
- and so on

Surely, we can achieve a random permutation of the numbers 1,2,... ,n easily by

sample(1:n, replace=FALSE)

For example

> set.seed(0); sample(1:5, replace=FALSE)
[1] 1 4 3 5 2

However, I want to get similar results manually according to the above algorithmic steps. Then I try

## write the function
my_perm = function(n){ 
x = 1:n # initialize
k = n  #  position n
out = NULL
while(k>0){
  y = sample(x, size=1) # choose one of the numbers at random
  out = c(y,out) # put the number in position
  x = setdiff(x,out)  # the remaining numbers
  k = k-1 # and so on
}
out
}

## test the function
n = 5; set.seed(0); my_perm(n) # set.seed for reproducible

and have

[1] 2 2 4 5 1

which is obviously incorrect for there are two 2 . How can I fix the problem?

user_3962914 · Answer

You have implemented the logic correctly but there is only one thing that you need to be aware which is related to R.

From ?sample

If x has length 1, is numeric (in the sense of is.numeric) and x >= 1, sampling via sample takes place from 1:x

So when the last number is remaining in x, let's say that number is 4, sampling would take place from 1:4 and return any 1 number from it.

For example,

set.seed(0)
sample(4, 1)
#[1] 2

So you need to adjust your function for that after which the code should work correctly.

my_perm = function(n){ 
  x = 1:n # initialize
  k = n  #  position n
  out = NULL
  while(k>1){ #Stop the while loop when k = 1
    y = sample(x, size=1) # choose one of the numbers at random
    out = c(y,out) # put the number in position
    x = setdiff(x,out)  # the remaining numbers
    k = k-1 # and so on
  }
  out <- c(x, out) #Add the last number in the output vector.
  out
}

## test the function
n = 5
set.seed(0)
my_perm(n)
#[1] 3 2 4 5 1

user_14587041 · Answer

Sample size should longer than 1. You can break it by writing a condition ;

my_perm = function(n){ 
x = 1:n 
k = n  
out = NULL
while(k>0){
  if(length(x)>1){
     y = sample(x, size=1) 
  }else{
      y = x
  }
   
  out = c(y,out)
  x = setdiff(x,out)
  k = k-1 
}
out
}

n = 5; set.seed(0); my_perm(n)


[1] 3 2 4 5 1

Generating a Random Permutation in R

2 Answers