如何选择总和为n的元素？

Question

说我有以下数据帧

x <- c("p1","p2","p3","p4","p5","p6","p7","p8","p9","p10")
y <- c(1,4,3,5,5,7,2,2,6,8)
df <- data.frame(x,y)

说x代表球员并y代表目标.比如说,我想要所有目标总和为10的玩家子集

{p1,p3,p9},{p3,p6},{p7,p8,p9}...

Answer 1

1)lpSolve这可以使用integert线性编程来完成.我们使用c(0,...,0)的目标和由y组成的一行矩阵作为约束矩阵.约束的右侧必须等于n,即10.

library(lpSolve)
y <- c(1,4,3,5,5,7,2,2,6,8)
n <- length(y)
k <- sum(cumsum(sort(y)) <= n) + 1 # upper bound to no of players in group
out <- lp(objective = numeric(n), 
   const.mat = matrix(y, 1), const.dir = "==", const.rhs = n,
   all.bin = TRUE, num.bin.solns = sum(choose(n, 1:k)))

# solution vector seems to have junk at end so truncate it and reshape to matrix
soln <- matrix(head(out$solution, n * out$num.bin.solns), n)

它共找到19个解决方案:

> out
Success: the objective function is 0 
         19 solutions returned

> out$num.bin.solns
[1] 19

> dim(soln)
[1] 10 19

列soln是可行的解决方案.例如,第一个solun是玩家1,2和4:

> soln[, 1]
 [1] 1 1 0 1 0 0 0 0 0 0
> which(soln[, 1]==1)
[1] 1 2 4

我们可以将解决方案列为如下字符串:

> x <- c("p1","p2","p3","p4","p5","p6","p7","p8","p9","p10")
> apply(soln == 1, 2, function(v) toString(x[v]))
 [1] "p1, p2, p4"     "p4, p5"         "p3, p4, p7"     "p1, p4, p7, p8"
 [5] "p1, p2, p3, p8" "p1, p2, p3, p7" "p1, p3, p9"     "p3, p4, p8"    
 [9] "p1, p2, p5"     "p3, p5, p7"     "p2, p9"         "p3, p5, p8"    
[13] "p3, p6"         "p1, p5, p7, p8" "p1, p6, p7"     "p1, p6, p8"    
[17] "p7, p8, p9"     "p8, p10"        "p7, p10"  

2)wle 第二种方法是将1:10的所有10 ^ 2子集创建为二进制向量v,然后选择那些y %*% v == 10(y来自问题的地方).这种方法产生简洁的代码,只要y不太长就可以.

library(wle)
m <- sapply(0:(2^10-1), function(x) binary(x, 10)$binary)
soln2 <- m[, y %*% m == 10]

如果首选表单,请使用与(1)中相同的方法将其转换为字符串向量.

更新:一些更正和改进并添加(2).