我有一个二元向量列表。从这个列表中,我想找到 n 个向量(不一定不同)(x,y),使得这些向量的 ys 之和大于或等于数字 k。如果有多个向量满足该条件,则选择xs之和最小的向量。
例如,我想找到 n=2 个向量 (x1,y1) 和 (x2,y2),使得 y1+y2 >= k。如果不止一个满足这个条件,则选择x1+x2最小的一个。
到目前为止,我只设法设置了以下代码:
X <- c(3, 2, 3, 8, 7, 7, 13, 11, 12, 12)
Y <- c(2, 1, 3, 6, 5, 6, 8, 9, 10, 9)
df <- data.frame(A, B)
l <- list()
for (i in seq(1:nrow(df))){
n <- as.numeric(df[i,])
l[[i]] <- n
}
使用上面的值,假设 n=1,k=9,那么我会选择元组 (x,y)=(11,9) 因为即使 (12,9) 也符合条件 y =k,x更小。
如果 n=2,k=6,那么我会选择 (x1,y1)=(3,3) 和 (x2,y2)=(3,3) 因为它是满足 y1 的最小 x1+x2 +y2 >= 6。
如果 n=2,k=8,那么我会选择 (x1,y1)=(3,3) 和 (x2,y2)=(7,5) 因为 y1+y2>=8 并且在下一个替代元组 (3,3) 和 (8,6),3+8=11 大于 3+7。
我觉得蛮力解决方案是可能的:每个向量与其余向量的所有可能的 n 大小组合,对于每个排列计算 yTotal=y1+y2+y3...找到满足 yTotal 的所有 yTotal 组合> =k 并从中选择 xTotal=x1+x2+x3... 最小的一个。
我确实很难将它放入 R 代码中,并且想知道它是否是正确的选择。感谢您的帮助!
最佳答案
首先,从您的问题看来,您允许从 Y 中进行选择并进行替换。该代码基本上采用您的蛮力方法:使用 gtools
库中的 permutations
生成排列。然后基本上对 sum(Y)>=k 进行过滤,并先按最小的 sum(Y) 排序,然后按 sum(X) 排序。
X <- c(3, 2, 3, 8, 7, 7, 13, 11, 12, 12)
Y <- c(2, 1, 3, 6, 5, 6, 8, 9, 10, 9)
n<-1
perm<-gtools::permutations(n=length(Y),r=n, repeats.allowed=T)
result<-apply(perm,1,function(x){ c(sum(Y[x]),sum(X[x])) })
dim(result) # 2 10
k=9 ## Case of n=1, k=9
keep<-which(result[1,]>=k)
result[,keep[order(result[1,keep],result[2,keep])[1]]] # 9 and 11
##### n=2 cases ##########
n<-2
perm<-gtools::permutations(n=length(Y),r=n, repeats.allowed=T)
result<-apply(perm,1,function(x){ c(sum(Y[x]),sum(X[x])) })
dim(result) # 2 100
## n=2, k=6
keep<-which(result[1,]>=6)
keep[order(result[1,keep],result[2,keep])[1]] # the 23 permutation
perm[23,] # 3 3 is (Y1,Y2)
result[,keep[order(result[1,keep],result[2,keep])[1]]] # sum(Y)=6 and sum(X)=6
## n=2, k=8
keep<-which(result[1,]>=8)
keep[order(result[1,keep],result[2,keep])[1]] # the 6 permutation
perm[6,] # 1 6 is (Y1,Y2)
result[,keep[order(result[1,keep],result[2,keep])[1]]] # sum(Y)=8 and sum(X)=10
关于r - 从聚合满足条件的列表中查找 n 个元组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43080926/