使用R中的递归查找所有组合

Question

我在从递归函数返回值时遇到问题，希望您能为我提供帮助。我有一个包含一堆矩阵的列表，每个矩阵代表一组可能的组合，并使用combn（）生成。例如，列表中可能是3个矩阵：

# set 1 has 4 elements, do nCk = 4C1:
set1 <- c("b2","b3","b4","b5")
set1 <- combn(set1,1,simplify = T)  

# set 2 has 3 elements, choose 2:
set2 <- c("c1","c2","b2")
set2 <- combn(set2,2,simplify = T)

# set 3 has 10 elements, choose 1:
set3 <- combn(c(1:10),1, simplify = T)

例如，如果要打印set2，它将有2行（选择2）和3列（3C2 = 3）：

> set2
     [,1] [,2] [,3]
[1,] "c1" "c1" "c2"
[2,] "c2" "b2" "b2"

我需要获得所有可能的4元素组合（上面每组1个元素）。我可以使用while循环并模拟状态机来执行此操作，但是该解决方案比较笨拙，需要较长的代码。我知道可以使用递归来完成此操作，因为我能够正确地print 120个组合（下面的代码），但是当尝试返回它们或将它们保存在变量中时，出现<font color="red">subscript out of bounds错误或结果重复数千次。我也想避免使用全局变量，它将被嵌入到一个相当大的项目中，所以我宁愿避免使用过多的变量来膨胀我的工作空间。

当然，在部署时，集合的数量将是动态的，并且每个集合的元素也会改变。集合也不太大，所以我很想实现一种递归方法！

要打印的工作代码：

combb <- function(allsets, number, carry){
  if(number>length(allsets)){
    print(carry)
    return()
  } else{
    for(j in 1:length(allsets[[number]][1,])){
      newcarry <- c(carry, allsets[[number]][,j])
      number2 <- number + 1
      combb(allsets, number2, newcarry)
    }
  }
}

谢谢！

Answer 1

我发现很难来回携带结果，因为它需要标志和列表或其他解决方案。相反，我要做的是创建包装函数，在其中创建了局部变量。递归函数在内部定义，并访问（“全局”）上述变量。然后，该变量由包装器返回：

combb <- function(allsets){

  carry <- integer(0)
  height <- 0L
  for (j in 1:length(allsets)) {
    height <- height + length(allsets[[j]][, 1])
  }

  output <- matrix(allsets[[1]][0, 1], nrow = height, ncol = 0)

  combb1 <- function(allsets, number, carry) {
    if(number > length(allsets)){
      output <<- cbind(output, carry, deparse.level = 0)
      return()
    } else{
      for (j in 1:length(allsets[[number]][1,])) {
        # Only add unique combinations (some combinations are vectors)
        if((TRUE %in% (allsets[[number]][, j] %in% carry)) == FALSE) {
          newcarry <- c(carry, allsets[[number]][, j], use.names = FALSE)
          number2 <- number + 1
          combb1(allsets, number2, newcarry)
        } else{
          next()
        }
      }
    }
  }

  combb1(allsets, 1, carry)

  return(output)
}

您可以从该解决方案中看到，递归很简洁（combb1函数），不会使任何全局/工作区变量杂乱无章。

Answer 2

我发现很难来回携带结果，因为它需要标志和列表或其他解决方案。相反，我要做的是创建包装函数，在其中创建了局部变量。递归函数在内部定义，并访问（“全局”）上述变量。然后，该变量由包装器返回：