Encontrar n tuplas de una lista cuya agregación satisface una condición: r, algoritmo, vector, optimización matemática, combinatoria

Tengo una lista de vectores de dos elementos. De esta lista, me gustaría encontrar n vectores (no necesariamente distintos) (x, y), de modo que la suma de las ys de estos vectores sea mayor o igual a un número k. Si varios vectores satisfacen esta condición, seleccione aquel donde la suma de las xs es la más pequeña.

Por ejemplo, me gustaría encontrar n = 2 vectores (x1, y1) y (x2, y2) de modo que y1 + y2> = k. Si hay más de uno que satisfaga esta condición, seleccione el que sea x1 + x2 es el más pequeño.

Hasta ahora solo he logrado configurar el siguiente código:

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
}

Usando los valores anteriores, supongamos que n = 1, k = 9, luego elegiré la tupla (x, y) = (11,9) porque aunque (12,9) también coincide con la condición de que y = k, la x es más pequeña.

Si n = 2, k = 6, entonces elegiré (x1, y1) = (3,3) y (x2, y2) = (3,3) porque es el x1 + x2 más pequeño que satisface y1 + y2> = 6.

Si n = 2, k = 8, entonces elegiré (x1, y1) = (3,3) y (x2, y2) = (7,5) porque y1 + y2> = 8 y en las siguientes tuplas alternativas (3,3) y (8,6), 3 + 8 = 11 es mayor que 3 + 7.

Siento que una solución de fuerza bruta seríaposible: todas las combinaciones posibles de tamaño n de cada vector con el resto, para cada permutación, calcule yTotal = y1 + y2 + y3 ... encuentre todas las combinaciones yTotal que satisfagan yTotal> = k y de ellas, elija aquella donde xTotal = x1 + x2 + x3 ... es mínimo.

Definitivamente me cuesta poner esto en el código R y me pregunto si es la opción correcta. ¡Gracias por su ayuda!

Respuestas

Primero, parece que a partir de su pregunta usted permite seleccionar de Y con reemplazo. El código básicamente hace su enfoque de fuerza bruta: use el permutations en el gtools biblioteca para generar las permutaciones. Luego, básicamente, realice el filtrado para sum (Y)> = k, y ordene primero por la suma más pequeña (Y) y luego 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