r-如何调用组合的输出，这些输出加起来就是某个数字

Question

我想看看下面返回的组合加起来至少有46个。我应该输入什么代码？

x=c(20,10,16,16,6,15)
L=combn(x,3)

L是6选3的组合列表。

谢谢！

Answer 1

试试这个

x <- c(20,10,16,16,6,15)
sum(combn(x, 3, sum) >= 46)

输出

[1] 6

Answer 2

这些类型的问题由程序包RcppAlgos^*解决。OP提到的具体问题涉及多集的组合，使用大多数标准工具，多集会产生许多重复条目(我认为这是不需要的(。

例如，天真的方法必须首先生成所有组合，求和值，然后检查所有值。请注意，我们没有利用FUN =论点进行演示：

x <- c(20,10,16,16,6,15)
funNaive <- function(x, m, tar) {
all_combs <- t(combn(x, m))
ind <- which(rowSums(all_combs) >= tar)
all_combs[ind, ]
}
funNaive(x, 3, 46)
[,1] [,2] [,3]
[1,]   20   10   16
[2,]   20   10   16   <- duplicate of the 1st row
[3,]   20   16   16
[4,]   20   16   15
[5,]   20   16   15   <- duplicate of the 4th row
[6,]   16   16   15

您将注意到，第1行和第2行与第3行和第4行是相同的。对于这个问题，总共应该只有4个结果。

这里有一个从RcppAlgos使用comboGeneral的更好方法。注意freqs参数的使用，该参数用于表示源向量的每个元素重复的次数：

funAlgos <- function(x, m, tar) {
x <- sort(x)
myFreq <- rle(x)$lengths
myVals <- rle(x)$values

RcppAlgos::comboGeneral(myVals, m,
freqs = myFreq,
constraintFun = "sum",
comparisonFun = ">=",
limitConstraints = tar)
}
funAlgos(x, 3, 46)
[,1] [,2] [,3]
[1,]   20   16   16
[2,]   20   16   15
[3,]   20   16   10
[4,]   16   16   15

您可以更改上面的基本方法以获得正确的结果。在这种情况下，我们仍然无法利用FUN =参数，因为我们需要能够删除重复的组合：

funNaiveCorrected <- function(x, m, tar) {
x <- sort(x)
all_combs <- t(combn(x, m))
no_dupes <- all_combs[!duplicated(all_combs), ]
ind <- which(rowSums(no_dupes) >= tar)
no_dupes[ind, ]
}
funNaiveCorrected(x, 3, 46)
[,1] [,2] [,3]
[1,]   20   10   16
[2,]   20   16   16
[3,]   20   16   15
[4,]   16   16   15

必须强调的是，我们不能简单地将unique应用于源向量，因为我们会错过具有重复值的组合。

对于小问题，这并不令人担忧，但对于较大的问题，这将迅速成为真正的瓶颈。观察：

set.seed(42)
big_x <- sort(sample(25, replace = TRUE))
system.time(algos <- funAlgos(big_x, 10, 175))
user  system elapsed 
0       0       0
dim(algos)
[1] 1668   10
system.time(naive <- funNaiveCorrected(big_x, 10, 175))
user  system elapsed 
17.161   0.276  17.434
dim(naive)
[1] 1668   10

对于更大的问题，基本方法将消耗所有可用内存。注意，不建议使用基本方法尝试以下示例(N.B.choose(50, 20) ~= 4.712921e+13(：

set.seed(1729)
huge_x <- sort(sample(50, replace = TRUE))
system.time(algos <- funAlgos(huge_x, 20, 800))
user  system elapsed 
0.009   0.001   0.010
dim(algos)
[1] 13473    20

^*我是RcppAlgos的作者

Answer 3

我认为解决这个问题的一个好方法是简单地转换生成的组合矩阵，找到和，并过滤那些加成46的组合。

transposeL<- as.data.frame(t(L)) %>% 
mutate(sum=V1+V2+V3) %>%
filter(sum>=46)

Answer 4

在Joe Erinjeri的答案的基础上，我们可以采用任何组合大小，并避免必须像这样写出变量名(V1、V2、V3…(：

library(tidyverse)
c(20,10,16,16,6,15) %>% 
combn(3) %>% 
t() %>% 
as.data.frame() %>% 
mutate(V_sum = rowSums(.)) %>%  
filter(V_sum >= 46) %>% 
nrow()

[1] 6