找到与目标相加的所有数字组合

Question

我希望找到最快的方法来找到1000个'n'整数的可能组合来找到目标整数.

例如.说我想要数字'20'.我想找到最多1000个四个整数的组合,它们总和到这个数字.整数可以重复.我还有一个条件,即整数不能小于特定的数字,在这种情况下为4.

target<-20  #the number I wish to sum to
lowest<-4   #the smallest integer I allow
size<-4 #the number of integers I wish to use to sum
maxposs <- target - ((size-1) * lowest) #given the lowest, this is the max possible integer. In my example it is 8.

这就是我开始解决这个问题的方法.利用combn找到的四个选择整数的所有组合,然后由那些和为我的目标过滤.

m <- combn(rep(lowest:maxposs,size), size)
m1<- m[,colSums(m)==target]

这里,'m1'有245列.只有这么多解决方案.最后几列:

#     [,238] [,239] [,240] [,241] [,242] [,243] [,244] [,245]
#[1,]      4      4      4      4      4      4      5      5
#[2,]      5      5      5      6      7      4      6      4
#[3,]      7      4      5      4      4      5      4      5
#[4,]      4      7      6      6      5      7      5      6

但是,在我的实际应用中,我可以处理非常高的整数(总计高达1000),并希望将自己限制为1000种可能组合的随机样本.由于这是一项随机统计检验,速度至关重要.我想知道是否有人知道更快的方法.我的方式感觉不直观.

Answer 1

my_matrix <- matrix(nrow = 1000, ncol = 4)
i <- 1
nn <- 1000
while(i <= 1000){
  x <- sample(x = 4:nn, size = 3)
  y = nn - sum(x)
  if(y >= 4){
    my_matrix[i, ] <- c(x, y)
    i <- i + 1
  }
}

按照加文的建议，请使用预先分配的矩阵重做。现在，它可以在.158秒内运行，速度快一倍，并且扩展性可能更好。