将数据存入数据库，直到达到最小样本大小并在R中找到所有排列

Question

这是一个示例。

df <- data.frame(item=letters[1:5], n=c(3,2,2,1,1))
df
  item n
1    a 3
2    b 2
3    c 2
4    d 1
5    e 1

项目需要分组，以便该组的样本大小至少为4。

如果按照df的排序，这将是解决方案。

  item n cluster
1    a 3       1
2    b 2       1
3    c 2       2
4    d 1       2
5    e 1       2

如何获得所有可能的独特解决方案？

此外，代码还不应允许任何聚类的样本大小小于4。

Answer 1

[下面，我们使用软件包partitions进行暴力破解。想法是找到df行的每个分区。然后，我们对每个组求和并检查是否满足要求。

df <- data.frame(item=letters[1:5], n=c(3,2,2,1,1))

minSize <- 4

funGetClusters <- function(df, minSize) {
    allParts <- partitions::listParts(nrow(df))

    goodInd <- which(sapply(allParts, function(p) {
        all(sapply(p, function(x) sum(df$n[x])) >= minSize)
    }))

    allParts[goodInd]
}

clusterBreakdown <- funGetClusters(df, minSize)

allDfs <- lapply(clusterBreakdown, function(p) {
    copyDf <- df
    copyDf$cluster <- 1L
    clustInd <- 2L

    for (i in p[-1]) {
        copyDf$cluster[i] <- clustInd
    }

    copyDf
})

这里是输出：

allDfs
[[1]]
  item n cluster
1    a 3       1
2    b 2       1
3    c 2       1
4    d 1       1
5    e 1       1

[[2]]
  item n cluster
1    a 3       1
2    b 2       2
3    c 2       2
4    d 1       1
5    e 1       1

[[3]]
  item n cluster
1    a 3       2
2    b 2       1
3    c 2       1
4    d 1       2
5    e 1       1

[[4]]
  item n cluster
1    a 3       2
2    b 2       1
3    c 2       1
4    d 1       1
5    e 1       2

[[5]]
  item n cluster
1    a 3       2
2    b 2       1
3    c 2       2
4    d 1       1
5    e 1       1

[[6]]
  item n cluster
1    a 3       2
2    b 2       2
3    c 2       1
4    d 1       1
5    e 1       1

应该注意的是，随着行数的增加，会发生组合爆炸。例如，仅用10行，我们就必须测试115975个不同的分区。

正如@chinsoon的评论，对于不太精确的解决方案，RcppAlgos可能是一个不错的选择。免责声明，我是作者。