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

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
  }
}

根据Gavin的建议，用预先分配的矩阵重做。现在，它以.158秒的速度运行，速度是原来的两倍，而且可能缩放得更好。