如何在更大的数据集上迭代执行组合？

Question

背景 - 我想尝试彻底搜索一组 250 行的所有可能组合，一次取 10 行。为了迭代地得到这个，我使用下面的代码

`
## Function definition
gen.next.cbn <- function(cbn, n){
  ## Generates the combination that follows the one provided as input
  cbn.bin      <- rep(0, n)
  cbn.bin[cbn] <- 1
  if (tail(cbn.bin, 1) == 0){
    ind <- tail(which(cbn.bin == 1), 1)
    cbn.bin[c(ind, ind+1)] <- c(0, 1)
  }else{
    ind <- 1 + tail(which(diff(cbn.bin) == -1), 1)
    nb  <- sum(cbn.bin[-c(1:ind)] == 1)
    cbn.bin[c(ind-1, (n-nb+1):n)] <- 0
    cbn.bin[ind:(ind+nb)]         <- 1
  }
  cbn <- which(cbn.bin == 1)
}

## Example parameters
n   <- 40
k   <- 10

## Iteration example
for (i in 1:choose(n, k)){
  if (i == 1){
    cbn <- 1:k
  }else{
    cbn <- gen.next.cbn(cbn, n)

  }
  print(cbn)


}


`

超过 40 行时出现错误 "cannot allocate vector of size n GB"。

理想解： a）如果可以转储组合并且可以在循环中的每个运行之后迭代地刷新内存（我可以在其中检查进一步的条件） b) 如果可以将组合转储到 csv 文件，这样它就不会导致内存占用。

感谢您的支持。

Answer 1

正如我在评论中所说，iterpc 是完成此类任务的方法。您首先需要通过 iterpc 函数初始化一个迭代器。接下来我们可以通过getnext生成下一个n组合。在此之后，我们只需将结果附加到 csv（或您喜欢的任何文件类型）。

getComboChunks <- function(n, k, chunkSize, totalCombos, myFile) {
    myIter <- iterpc(n, k)

    ## initialized myFile
    myCombs <- getnext(myIter, chunkSize)
    write.table(myCombs, file = myFile, sep = ",", col.names = FALSE)

    maxIteration <- (totalCombos - chunkSize) %/% chunkSize

    for (i in 1:maxIteration) {
        ## get the next "chunkSize" of combinations
        myCombs <- getnext(myIter, chunkSize)

        ## append the above combinations to your file
        write.table(myCombs, file = myFile, sep = ",",
                    col.names = FALSE , append = TRUE)
    }
}

例如，getComboChunks(250, 10, 100, 1000, "myCombos.csv") 一次将 250 选 10 的 1000 种组合写入文件 myCombos.csv 100 种组合。分块执行此操作比一次执行一个更有效。

这个库是用 C/C++ 编写的，因此它应该相当高效，但正如@Florian 在评论中指出的那样，它不会很快生成所有 gmp::chooseZ(250, 10) = Big Integer ('bigz') : [1] 219005316087032475 组合。我还没有测试过，但如果你满足于 200，选择 5，我想你将能够在一天之内产生它（它刚刚超过 25 亿个结果）。

如何在更大的数据集上迭代执行组合？

How to iteratively perform combinations on larger datasets?

r

dataset

combinations

combn