Permutation enumeration

[fcas80]

Hi. The following code from stackoverflow enumerates all permutations of a vector x. Please explain why this works. What the rbind statement is doing? Thanks.

getPerms <- function(x) {
if (length(x) == 1) {
return(x)
}
else {
res <- matrix(nrow = 0, ncol = length(x))
for (i in seq_along(x)) {
res <- rbind(res, cbind(x[i], Recall(x[-i])))
}
return(res)
}
}

getPerms(letters[1:3])

[technocrat]

@fcas80

What the rbind statement is doing

It's adding to the matrix of results.

Using this similar but more elegant version

perm <- function(v) {
  n <- length(v)
  if (n == 1) v
  else {
    X <- NULL
    for (i in 1:n) X <- rbind(X, cbind(v[i], perm(v[-i])))
    X
  }
}

perm(letters[1:3])
#>      [,1] [,2] [,3]
#> [1,] "a"  "b"  "c" 
#> [2,] "a"  "c"  "b" 
#> [3,] "b"  "a"  "c" 
#> [4,] "b"  "c"  "a" 
#> [5,] "c"  "a"  "b" 
#> [6,] "c"  "b"  "a"

^{Created on 2020-10-18 by the reprex package (v0.3.0.9001)}

if traps for a single element vector

for (i in 1:n) X <- rbind(X, cbind(v[i], perm(v[-i])))

populates a matrix by iterating over the length of the vector and taking its element at each step and creating a row in X (initially NULL) with the value of that element and, the elegant part, recursively calling itself to create the columns with the remaining possibilities with the elements less that that which starts the row.

[fcas80]

Technocrat, thank you.

I think this might be clearer if I could use X outside of the function. How do I make X a global variable?

[technocrat]

# use global X as an argument
X <- NULL
perm <- function(v,X=X) {
  n <- length(v)
  if (n == 1) v
  else {
    X <- NULL
    for (i in 1:n) X <- rbind(X, cbind(v[i], perm(v[-i])))
    X
  }
}

perm(letters[1:3],X)

Because X is merely a placeholder object it can be initialized within either the global environment or the function; within the globql environment is an extra step. Generally, functions should return a value rather than manipulate a global object in situ/

[joels]

Were you asking just to understand the code? If you're looking for an efficient way to generate permutations, you could use permn from the combinat package:

library(combinat)

v = letters[1:3]

# Returns a list
permn(v)

# If you want a matrix
do.call("rbind", permn(v))

[fcas80]

Can we put the contents of X in a dataframe and then use the dataframe outside the function?

[technocrat]

> data.frame(perm(letters[1:3]))
  X1 X2 X3
1  a  b  c
2  a  c  b
3  b  a  c
4  b  c  a
5  c  a  b
6  c  b  a

[nirgrahamuk]

you can assign the result of a function to a variable name in the calling scope

myvar <- myfunc(someparm)