在没有包的情况下查找 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

但是有几件事是 less-efficient:

R 做的 tail-recursion 不是很好，所以理论上这可以填充调用堆栈并耗尽 R；和
这是我在中关于迭代调用 rbind 中建议不做的事情。
是error-prone：如果你用n < start或n==0调用，那么它会失败。

而且很有可能：

如果您不能以这种方式使用 factorial，您可以用 prod(1:n) 模棱两可。下面的其余功能将使用此 prod 方法，交给您首选。
factorial 和 prod 都将以非常高的 n 开始失败，可能远远超出您要用于此作业的限制。在这些数字下，可能需要进入 gamma 领域，more-efficient 计算高 n 阶乘（并且可能需要直到 R 完全达到 64-bit-integer友好）。

修复其中一些问题的迭代可能是

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

坦率地说，在 i 和 j.

上使用一些巧妙的数学运算可以摆脱 r 计数器

但是在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

一个区别（pre-mitigated 前导 if/return）是 seq_len 的使用：如果你想要一个长度为 n，那么 1:n 只有 n >= 1 才是准确的。如果n为0，那么1:0产生一个长度为2的向量，这不是你应该得到的；取而代之的是 seq_len(0) returns 长度为 0 的向量，更加一致。

这仍然不是 "efficient" 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 循环的情况下生成这个 ，但它需要更多的矢量化魔法，这两者都超出了这个任务的范围并且超出了我用于本课的时间。

在没有包的情况下查找 1:n 个数字的所有唯一组合

Finding all unique combinations of 1:n numbers without packages

r

combn