r - 将数据库中的项目池化，直到达到最小样本量并找到 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 可能是较大案例的可接受解决方案的不错选择。免责声明，我是作者。我已经回答了类似的问题，但输入的信息要多得多，并且取得了很好的成功。

• Allocating tasks to parallel workers so that expected cost is roughly equal
• Split a set into n unequal subsets with the key deciding factor being that the elements in the subset aggregate and equal a predetermined amount?
  • @AllanCameron 也有一个很好的答案和很好的方法来解决这个问题。你也应该读一读。

最后，Robin K. S. Hankin(partitions 包的作者)和 Luke J. West 的以下小插图不仅值得一读，而且非常适用于此处介绍的问题。

• Set Partitions in R