CODEWITHSUNDEEP
rcombinationscombinatorics
FairyOnIce
FairyOnIce

Reputation: 2614

R: function that returns all the possible ordering of n elements?

In R, is there a function that returns all the possible ordering of n elements? I want a n! by n matrix such that each row contains all the possible ordering index of n elements. That is, if n = 3, I want:

 1,2,3 
 1,3,2,
 2,1,3,
 2,3,1,
 3,1,2,
 3,2,1

I first thought expand.grid does this job, and tried:

n <- 3
expand.grid(rep(list(1:n),n))

   Var1 Var2 Var3
1     1    1    1
2     2    1    1
3     3    1    1
4     1    2    1
5     2    2    1
6     3    2    1
7     1    3    1
8     2    3    1
9     3    3    1
10    1    1    2
11    2    1    2
12    3    1    2
13    1    2    2
14    2    2    2
15    3    2    2
16    1    3    2
17    2    3    2
18    3    3    2
19    1    1    3
20    2    1    3
21    3    1    3
22    1    2    3
23    2    2    3
24    3    2    3
25    1    3    3
26    2    3    3
27    3    3    3

but this returns 3^3 by 3 matrix, each row could possibly contains duplicate values...

Upvotes: 3

Views: 188

Answers (3)

ruggero
ruggero

Reputation: 440

Here are some options:

n = 3

library(gtools)
permutations(n,n)

library(combinat)
permn(1:n)

library(multicool)
m = initMC(1:n)
allPerm(m)

library(iterpc)
I = iterpc(n, ordered = TRUE)
getall(I)

Let's do some benchmarking

n=5
I = iterpc(n, ordered = TRUE)
m=initMC(1:n)

library(microbenchmark)
microbenchmark( permutations(n,n), permn(1:n), allPerm(m), getall(I) )

# Unit: microseconds
#               expr      min        lq    median        uq      max neval
# permutations(n, n) 2781.110 2857.9100 2922.7635 2973.5835 4877.656   100
#         permn(1:n) 3600.310 3664.0255 3722.6210 3772.4940 5475.748   100
#         allPerm(m)  325.026  458.1460  503.6575  558.8390  719.835   100
#          getall(I)  169.151  189.0615  245.5715  284.8245  472.937   100

permutations from gtools and permn from cobinat are written in R, while the other two in C, so are much faster.
Besides, multicool provides an algorithm specifically designed for permutations of multiset. So it seems that iterpc is a better choice for simple permutations:

f1 <- function(n){
m=initMC(1:n)
allPerm(m)}

f2 <- function(n){
I = iterpc(n, ordered = TRUE)
getall(I)}

microbenchmark(f1(10),f2(10))

# Unit: milliseconds
#   expr       min        lq    median        uq       max neval
# f1(10) 1143.8057 1216.4617 1322.2973 1335.5547 1383.8723   100
# f2(10)  421.7535  457.3466  461.4995  551.4025  648.8821   100

Upvotes: 5

Colonel Beauvel
Colonel Beauvel

Reputation: 31171

Another package for this, combinat, where permn returns a list and can be converted to matrix using the below:

library(combinat)
t(simplify2array(permn(1:3)))

#     [,1] [,2] [,3]
#[1,]    1    2    3
#[2,]    1    3    2
#[3,]    3    1    2
#[4,]    3    2    1
#[5,]    2    3    1
#[6,]    2    1    3

Upvotes: 2

akrun
akrun

Reputation: 887391

Try

library(gtools)
permutations(n,3)
#     [,1] [,2] [,3]
#[1,]    1    2    3
#[2,]    1    3    2
#[3,]    2    1    3
#[4,]    2    3    1
#[5,]    3    1    2
#[6,]    3    2    1

Upvotes: 7

Related Questions