如何使用 R 中的递归创建长度为 n 的所有 2^n 个二进制序列的矩阵？

Question

我知道我可以为此使用 expand.grid，但我正在努力学习实际的编程。我的目标是利用下面的内容并使用递归来获取所有长度为 n 的 2^n 个二进制序列。

我可以对 n = 1 执行此操作，但我不明白如何以递归方式使用相同的函数来获得更高维度的答案。

这里是 n = 1:

binseq <- function(n){
  binmat <- matrix(nrow = 2^n, ncol = n)
  r <- 0 #row counter
  for (i in 0:1) {
        r <- r + 1
        binmat[r,] <- i
    }
  return(binmat)
  }

我知道我可能必须在 return 语句中使用 cbind。我的直觉告诉我 return 语句应该类似于 cbind(binseq(n-1), binseq(n))。但是，老实说，我现在完全迷路了。

所需的输出应该产生类似于 expand.grid 给出的结果：

n = 5
expand.grid(replicate(n, 0:1, simplify = FALSE))

它应该只是一个矩阵，因为 binmat 正在递归填充。

Answer 1

根据评论（下方）的要求，这里是二进制序列的有限实现：

eg.binary <- function(n, digits=0:1) {
  if (n <= 0) return(matrix(0,0,0))
  if (n == 1) return(matrix(digits, 2))
  x <- eg.binary(n-1)
  rbind(cbind(digits[1], x), cbind(digits[2], x))
}

处理完R无法正确处理的初始情况后，处理n=1的"base case"，然后递归获取所有n-1位二进制字符串，并在每个数字前添加给他们每个人。这些数字被添加到前面，以便二进制字符串以其通常的字典顺序结束（与 expand.grid 相同）。

示例：

eg.binary(3)

     [,1] [,2] [,3]
[1,]    0    0    0
[2,]    0    0    1
[3,]    0    1    0
[4,]    0    1    1
[5,]    1    0    0
[6,]    1    0    1
[7,]    1    1    0
[8,]    1    1    1

下面是一般性解释（具有更灵活的解决方案）。

将问题归结为将数组 y 的值添加到数据帧 X 的行上的基本操作，将 X 的整个副本与每个值相关联(via cbind) 并附加整个批次 (via rbind):

cross <- function(X, y) {
  do.call("rbind", lapply(y, function(z) cbind(X, z)))
}

例如，

cross(data.frame(A=1:2, b=letters[1:2]), c("X","Y"))

  A b z
1 1 a X
2 2 b X
3 1 a Y
4 2 b Y

（我们稍后再考虑列名。）

此类数组列表的递归解决方案y 假定您已经对列表的最后一个元素以外的所有元素执行了这些操作。它必须从某个地方开始，这显然包括将数组转换为单列数据框。因此：

  eg_ <- function(y) {
    n <- length(y)
    if (n <= 1) {
      as.data.frame(y) 
    } else {
      cross(eg_(y[-n]), y[[n]])
    }
  }

为什么这个名字好笑？因为我们可能想要做一些 post-processing，比如给结果起个好听的名字。这是一个更完整的实现：

eg <- function(y) {
  # (Define `eg_` here to keep it local to `eg` if you like)
  X <- eg_(y)
  names.default <- paste0("Var", seq.int(length(y)))
  if (is.null(names(y))) {
    colnames(X) <- names.default
  } else {
    colnames(X) <- ifelse(names(y)=="", names.default, names(y))
  }
  X
}

例如：

eg(replicate(3, 0:1, simplify=FALSE))

  Var1 Var2 Var3
1    0    0    0
2    1    0    0
3    0    1    0
4    1    1    0
5    0    0    1
6    1    0    1
7    0    1    1
8    1    1    1

eg(list(0:1, B=2:3))

Answer 2

显然这是所需的递归代码：

binseq <- function(n){
  if(n == 1){
    binmat <- matrix(c(0,1), nrow = 2, ncol = 1)
  }else if(n > 1){
    A <- binseq(n-1)
    B <- cbind(rep(0, nrow(A)), A)
    C <- cbind(rep(1, nrow(A)), A)
    binmat <- rbind(B,C)
  }
  return(binmat)
  }

基本上，对于 n = 1，我们创建一个 [0, 1] 矩阵。对于之后的每个 n，我们向原始矩阵添加一列 0，并分别添加一列 1。然后我们将两个矩阵rbind得到最终的产品。所以我明白了算法在做什么，但我并不真正理解递归在做什么。比如根据算法从n = 2到n = 3的步骤我就没看懂

如何使用 R 中的递归创建长度为 n 的所有 2^n 个二进制序列的矩阵？

How to create matrix of all 2^n binary sequences of length n using recursion in R?

r

recursion

combinatorics

binary-data