我希望找到最快的方法来找到多达 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 个可能组合的随机样本中。 由于这是随机统计测试,因此速度至关重要。我想知道是否有人知道更快的方法来做到这一点。我的方式感觉不是直觉上的快。
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 秒内运行,速度是原来的两倍,并且可能扩展得更好。