Поиск всех уникальных комбинаций чисел 1: n без пакетов

Question

Мне нужно создать функцию, которая предоставит мне все возможные комбинации чисел 1: n.Аргументом функции является n.Мне нужно сделать это без использования функции combn или какой-либо другой предварительно установленной функции в R.,Нижняя часть просто использует combn, чтобы проверить, работает ли вышеуказанная функция.

Я сделал следующее, но, очевидно, это не совсем правильный путь.

pairwise_comp <- function(n) {

res <- matrix(nrow = 0, ncol = 2)
for (i in 1:n) {
  res <-rbind(res,cbind( i , i+1))
}


  return(res)

}

Answer 1

Есть несколько способов атаковать, некоторые эффективные, некоторые читаемые (субъективные), но не многие из них оба.

Например, вы можете сделать это рекурсивно , вот так:

pairwise_recur <- function(n, start = 1) {
  if (n == start) return()
  nrows <- factorial(n) / (factorial(2) * factorial(n-2))
  res <- matrix(nrow = nrows, ncol = 2)
  rbind(
    cbind(rep(start, times = n - start),
          1 + start:(n-1)),
    pairwise_recur(n, start = start + 1)
  )
}
pairwise_recur(4)
#      [,1] [,2]
# [1,]    1    2
# [2,]    1    3
# [3,]    1    4
# [4,]    2    3
# [5,]    2    4
# [6,]    3    4

Но некоторые вещи по этому поводу менее эффективны:

1. R не очень хорошо выполняет хвостовую рекурсию, поэтому теоретически это может заполнить стек вызовов и исчерпать R; и
2. Это делает то, что я предложил , а не сделать в мой комментарий о повторном вызове rbind.
3. Он подвержен ошибкам: если вы позвоните с n < start или n==0, произойдет сбой.

И вполне возможно:

4. Если вы не можете использовать factorial таким образом, вы можете обозначить его как prod(1:n). Остальные функции ниже будут использовать этот метод prod, который вам предпочтительнее.
5. И factorial, и prod начнут давать сбой с очень высоким n, вероятно, намного превышающим предел, который вы собираетесь использовать для этого назначения. При этих числах, вероятно, будет необходимо перейти в область gamma, более эффективные вычисления для факториалов с высоким n (и, вероятно, необходимо, пока R не станет полностью дружественным к 64-битным целым числам).

---

Итерация, которая исправляет некоторые из них, может быть

pairwise_iter <- function(n) {
  nrows <- prod(1:n) / ( prod(1:2) * prod(1:(n-2)) )
  res <- matrix(nrow = nrows, ncol = 2)
  r <- 0
  for (i in 1:(n-1)) {
    for (j in (i+1):n) {
      r <- r + 1
      res[r,1] <- i
      res[r,2] <- j
    }
  }
  res
}
# same output

И, честно говоря, можно избавиться от счетчика r с помощью некоторой умной математики на i и j.

Но это все еще склонно к проблемам, когда n < 3. Это может быть смягчено с помощью:

pairwise_iter2 <- function(n) {
  if (n <= 1) return(matrix(nrow = 0, ncol = 2))
  nrows <- prod(seq_len(n)) / ( prod(1:2) * prod(seq_len(n-2)) )
  res <- matrix(nrow = nrows, ncol = 2)
  r <- 0
  for (i in 1:(n-1)) {
    for (j in (i+1):n) {
      r <- r + 1
      res[r,1] <- i
      res[r,2] <- j
    }
  }
  res
}

pairwise_iter2(0)
#      [,1] [,2]
pairwise_iter2(1)
#      [,1] [,2]
pairwise_iter2(2)
#      [,1] [,2]
# [1,]    1    2
pairwise_iter2(3)
#      [,1] [,2]
# [1,]    1    2
# [2,]    1    3
# [3,]    2    3

Одним отличием (которое предварительно смягчается лидирующим if / return) является использование seq_len: если вам нужна последовательность длиной n, то 1:n точен только до тех пор, пока как n >= 1. Если n равно 0, то 1:0 создает вектор длины 2, а это не то, что вы должны получить; вместо этого seq_len(0) возвращает вектор длины 0, что более согласованно.

---

Это все еще не "эффективно" в R способе ведения дел. Для этого вы можете удалить внутренний цикл for и назначить по векторам:

pairwise_vec1 <- function(n) {
  if (n <= 1) return(matrix(nrow = 0, ncol = 2))
  nrows <- prod(seq_len(n)) / ( prod(1:2) * prod(seq_len(n-2)) )
  res <- matrix(nrow = nrows, ncol = 2)
  r <- 0
  for (i in 1:(n-1)) {
    vec <- seq_len(n - i)
    res[r + vec, 1] <- i
    res[r + vec, 2] <- i + vec
    r <- r + length(vec)
  }
  res
}

На самом деле можно сгенерировать без даже без внешнего цикла for, но для этого требуется немного больше векторизованного волшебства, которое как выходит за рамки этого задания, так и выходит за рамки моего времени этот урок.