r - 从聚合满足条件的列表中查找 n 个元组

Question

我有一个二元向量列表。从这个列表中，我想找到 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 代码中，并且想知道它是否是正确的选择。感谢您的帮助!

Answer 1

首先，从您的问题看来，您允许从 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