集計が条件を満たすリストからnタプルを見つける

Question

私は2要素ベクトルのリストを持っています。このリストから、n個のベクトル（必ずしも区別できるとは限りません）（x、y）を見つけて、これらのベクトルのyの和がkより大きいか等しいようにしたいと思います。複数のベクトルがこの条件を満たす場合は、xsの和が最小のものを選択します。

たとえば、y1 + y2> = kとなるn = 2個のベクトル（x1、y1）と（x2、y2）を探したいとします。この条件を満たすものが1つ以上ある場合は、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 
} 

（Xさんは1、K = 9、その後、私はタプルを選ぶだろう、N =ましょう：

は、私がこれまでのところだけ、次のコードを、設定するために管理してきました、y）=（11,9）であるが、（12,9）がy = kである条件にも合致するにもかかわらず、xはより小さいからである。

n = 2、k = 6の場合、（x1、y1）=（3,3）と（x2、y2）=（3,3）を選択します。これはx1 + y1 + y2> = 6.

n = 2、k = 8の場合、（x1、y1）=（3,3）と（x2、y2）=（7,5） + y2> = 8であり、次の代替タプル（3,3）および（8,6）では、3 + 8 = 11は3 + 7より大きい。

残念ながら、各ベクトルのn倍の可能なすべての組み合わせを、各置換ごとに計算します。yTotal = y1 + y2 + y3 ...すべてを見つけるy y合計を満たす合計の組み合わせ> = kそしてそれらのうち、xTotal = x1 + x2 + x3 ...が最小であるものを選んでください。

私はこれをRコードに入れて苦労し、それが正しい選択であるかどうか疑問に思います。ご協力ありがとうございました！

Answer 1

まず、Yから置換を選択することを許可しているようです。コードは基本的にあなたのブルートフォースアプローチを行います：gtoolsライブラリのpermutationsを使って順列を生成します。そして、基本的にsum（Y）> = kのフィル​​タリングを行い、最初に最小和（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