Generating a Random Permutation in R-CodePudding

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?

CodePudding user response：

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

CodePudding user response：

Sample size should longer than 1. You can break it by writing an 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