时间戳

首页 > 解决方案 > 在 R 中使用递归查找所有组合

r - 在 R 中使用递归查找所有组合

问题描述

我在从递归函数返回值时遇到问题，希望你能帮助我。我有一个包含一堆矩阵的列表，每个矩阵代表一组可能的组合并使用 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 循环并模拟状态机来做到这一点，但是该解决方案很笨拙并且代码很长。我知道这可以使用递归来完成，因为我能够正确打印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)
    }
  }
}

谢谢！

标签： rrecursioncombinatorics

解决方案

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

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 函数）并且不会弄乱任何全局/工作区变量。

推荐阅读