使用R查找所有小于给定数字的3个数字组合

Question

我有以下一组数字10、17、5、7、15。从这些数字中，我需要找到总和小于或等于35的所有3个数字组合。在一个这样的组合中，特定数字不应包含一次以上。例如：10，10，5是不正确的组合，因为10重复了两次。

我尝试了这段代码，但没有给出我所需要的。

library(data.table)
df=expand.grid(x1=c(10,17,5,7,15),
               x2=c(10,17,5,7,15),
               x3=c(10,17,5,7,15)
               )
setDT(df)
df[(x1+x2+x3) <= 35]

上面代码输出的一部分如下，

  x1 x2 x3
 1: 10 10 10
 2:  5 10 10
 3:  7 10 10
 4: 15 10 10
 5:  5 17 10
 6:  7 17 10
 7: 10  5 10

根据上述输出，可以看到一个数字出现了多次。任何人都可以建议获得预期结果的提示吗？

谢谢

Answer 1

尝试以下操作，查看问题是否出在其中。

x <- c(10,17,5,7,15)
i <- combn(x, 3, sum) <= 35

combn(x, 3)[, i]
#     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#[1,]   10   10   10   10   10   17    5
#[2,]   17   17    5    5    7    5    7
#[3,]    5    7    7   15   15    7   15

以上是总体思路。下面是一个更有效的实现，包括内存和速度f2。

f1 <- function(x, n = 3, thres = 35){
  i <- combn(x, n, sum) <= thres
  combn(x, n)[, i]
}
f2 <- function(x, n = 3, thres = 35){
  cmb <- combn(x, n)
  cmb[, colSums(cmb) <= thres]
}

检查结果是否全部具有不同的数字。

res <- f2(x)
apply(res, 2, function(y){
  all(y[-1] != y[1])
})
#[1] TRUE TRUE TRUE TRUE TRUE TRUE TRUE

identical(f1(x), f2(x))
#[1] TRUE

现在计时功能。

microbenchmark::microbenchmark(f1 = f1(x), 
                               f2 = f2(x))
#Unit: microseconds
# expr     min      lq      mean   median      uq     max neval cld
#   f1 105.150 107.383 110.66616 108.6535 109.896 238.899   100   b
#   f2  62.779  65.568  67.65754  66.4290  67.145 122.119   100  a 

Answer 2

comboGeneral软件包中的功能RcppAlgos（我是作者）是专门为此任务设计的。

library(RcppAlgos)
x <- c(10,17,5,7,15)

comboGeneral(x, 3, 
             constraintFun = "sum",
             comparisonFun = "<=",
             limitConstraints = 35)
     [,1] [,2] [,3]
[1,]    5    7   10
[2,]    5    7   15
[3,]    5    7   17
[4,]    5   10   15
[5,]    5   10   17
[6,]    7   10   15
[7,]    7   10   17

这也是非常有效的。观察：

set.seed(42)
s <- sample(100, 25)
s
[1] 92 93 29 81 62 50 70 13 61 65 42 91 83 23 40 80 88 10 39 46 73 11 78 85  7

system.time(a <- comboGeneral(s, 10, 
                              constraintFun = "sum",
                              comparisonFun = "<=",
                              limitConstraints = 600))
 user  system elapsed 
0.232   0.046   0.278

dim(a)
[1] 2252362      10

与f2@RuiBarradas和dt_checker@Cole 发布的更有效的函数相比：

system.time(b <- f2(s, 10, 600))
 user  system elapsed 
3.283   0.093   3.418

system.time(a2 <- dt_checker(s, 10, 600))
 user  system elapsed 
1.803   0.319   0.646

还应该注意的是，comboGeneral只要能获得更长的解，后面的算法就会终止。因此，在不同的约束条件下，时间会有所不同。观察：

system.time(a <- comboGeneral(s, 10, 
                              constraintFun = "sum",
                              comparisonFun = "<=",
                              limitConstraints = 400))
 user  system elapsed 
0.003   0.001   0.003

但是，使用其他解决方案时，必须先创建所有组合然后进行过滤（这不会花很长时间），因此时序与之前相似。

system.time(b <- f2(s, 10, 400))
 user  system elapsed 
2.933   0.039   2.973

system.time(a2 <- dt_checker(s, 10, 400))
 user  system elapsed 
1.786   0.276   0.627

作为最终基准，我们对在多个约束条件下的所有结果进行基准测试：

system.time(a <- lapply(seq(200, 600, 25), function(x) {
    t <- comboGeneral(s, 10, 
                      constraintFun = "sum",
                      comparisonFun = "<=",
                      limitConstraints = x)
    dim(t)
}))
 user  system elapsed 
0.498   0.125   0.623

system.time(a2 <- lapply(seq(200, 600, 25), function(x) {
    t <- dt_checker(s, 10, x)
    dim(t)
}))
  user  system elapsed 
34.448   4.633  10.693

identical(a, a2)
[1] TRUE