# @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)

CiMgQHJldHVybiBjKGFbMV0sIC4uLiwgYVtpXSwgYiwgYVtpKzFdLCAuLi4pCmluc2VydCA8LSBmdW5jdGlvbihhLCBiLCBpKSB7CiAgaWYgKGkgPT0gMCkgewogICAgcmV0dXJuKGMoYixhKSkKICB9IGVsc2UgaWYgKGkgPT0gbGVuZ3RoKGEpKSB7CiAgICByZXR1cm4oYyhhLGIpKQogIH0gZWxzZSB7CiAgICByZXR1cm4oIGMoYVsxOmldLCBiLCBhWyhpKzEpOmxlbmd0aChhKV0pICkKICB9Cn0KCiMgQHJldHVybiDkuIDlgItsaXN054mp5Lu2LCDljIXlkKvmiYDmnIkxLDIsLi4uLG7nmoTntYTlkIgKcGVybXV0YXRpb24gPC0gZnVuY3Rpb24obikgewogIHJldHZhbCA8LSBsaXN0KCkKICBpZiAobj09MSkgewogICAgcmV0dmFsW1sxXV0gPC0gMQogICAgcmV0dXJuKHJldHZhbCkKICB9CiAgdGVtcCA8LSBwZXJtdXRhdGlvbihuLTEpCiAgcmV0dmFsIDwtIHJlcCh0ZW1wLCBuKQogIGluZGV4IDwtIDEKICBmb3IoaSBpbiAwOihuLTEpKSB7CiAgICBmb3IoaiBpbiAxOmxlbmd0aCh0ZW1wKSkgewogICAgICByZXR2YWxbW2luZGV4XV0gPC0gaW5zZXJ0KHJldHZhbFtbaW5kZXhdXSwgbiwgaSkKICAgICAgaW5kZXggPC0gaW5kZXggKyAxCiAgICB9CiAgfQogIHJldHVybihyZXR2YWwpCn0KCnBlcm11dGF0aW9uKDQp