# @return c(a[1], ..., a[i], b, a[i+1], ...)
insert <- function(a, b, i) {
  if (i == 0) {
    return(c(b,a))
  } else if (i == length(a)) {
    return(c(a,b))
  } else {
    return( c(a[1:i], b, a[(i+1):length(a)]) )
  }
}

# @return 一個list物件, 包含所有1,2,...,n的組合
permutation <- function(n) {
  retval <- list()
  if (n==1) {
    retval[[1]] <- 1
    return(retval)
  }
  temp <- permutation(n-1)
  retval <- rep(temp, n)
  index <- 1
  for(i in 0:(n-1)) {
    for(j in 1:length(temp)) {
      retval[[index]] <- insert(retval[[index]], n, i)
      index <- index + 1
    }
  }
  return(retval)
}

permutation(4)