一旦达到目标总和就提取数值的每个组合

Question

我有一个两列的数据框，如下所示：

姓名	薪资
姓名1	5000000
姓名2	7000000
姓名3	9000000
名字4	12000000
名字5	14000000

我想找到工资达到 20,000,000 的所有组合。它可以超过 20,000,000，但一旦超过，它就会停止。例如，名称 1、2 和 3 是有效组合，名称 4 和 5 也是有效组合。

我也希望能够在数据框中查看薪资组合及其同事姓名。

请注意，我的数据帧通常在 30 个不同的数据帧中有大约 12 到 15 个名称。

到目前为止，我已经尝试过使用combn()，但据我所知，我只能选择一个特定的数字“m”，并且在组合停止时无法选择目标数字。我也无法使用“sets”包。

Answer 1

如果我正确理解你的目标，可能双

for

循环可以帮助解决你的问题

f <- function(df, target) {
  v <- with(df, sort(setNames(Salary, Name)))
  res <- list()
  for (p in seq_len(length(v) - 1)) {
    s <- v[p]
    idx <- p
    for (q in (p + 1):length(v)) {
      if (s + v[q] < target) {
        s <- s + v[q]
        idx <- c(idx, q)
      } else {
        idx <- c(idx, q)
        break
      }
    }
    for (k in seq_along(res)) {
      if (all(idx %in% res[[k]])) {
        res[[k]] <- NULL
      }
    }
    res <- c(Filter(length, res), list(idx))
  }
  Map(`[`, list(names(v)), res)
}

这样

> f(df, target = 20e6)
[[1]]
[1] "Name1" "Name2" "Name3"

[[2]]
[1] "Name3" "Name4"

[[3]]
[1] "Name4" "Name5"

Answer 2

这是一种枚举所有组合并选择可行组合的方法。请注意，这是非常低效的，因为一次就可以编写一个短路的函数。即，如果我知道所有 3 个组合都大于目标，则无需进行 4、5、6 等组合。另外，如果我知道子集大于目标，则无需进行包含该特定子集的任何组合。我忽略了所有这些，因此为什么我说该方法效率低下：

g <- function(df){
    n <- seq_len(nrow(df))
    fn <- \(x)if(sum(cumsum(df$Salary[x])>20e6) == 1)df$Name[x]
    gn <- \(x)Filter(length, combn(n, x, fn, simplify = FALSE))
    unlist(sapply(n, gn), FALSE)
 }

g(df)
[[1]]
[1] "Name 2" "Name 5"

[[2]]
[1] "Name 3" "Name 4"

[[3]]
[1] "Name 3" "Name 5"

[[4]]
[1] "Name 4" "Name 5"

[[5]]
[1] "Name 1" "Name 2" "Name 3"

[[6]]
[1] "Name 1" "Name 2" "Name 4"

[[7]]
[1] "Name 1" "Name 2" "Name 5"

[[8]]
[1] "Name 1" "Name 3" "Name 4"

[[9]]
[1] "Name 1" "Name 3" "Name 5"

[[10]]
[1] "Name 1" "Name 4" "Name 5"

[[11]]
[1] "Name 2" "Name 3" "Name 4"

[[12]]
[1] "Name 2" "Name 3" "Name 5"

[[13]]
[1] "Name 2" "Name 4" "Name 5"