r 自身项非和的向量

Question

我正在尝试构建一个函数来创建一个向量，其中任何项目都不是列表中其他项目的任何组合的总和（没有重复）。

此功能可以完成工作，但速度很慢...关于如何改进它有什么好的想法吗？

sum_fun <- function(k)
{
  out_list <- c(2,3,4)
  new_num <- 4

  while(length(out_list) < k)
  {
    new_num <- new_num + 1
    #Check if new_num can be written as a sum of the terms in out_list
    new_valid <- T
    for (i in 2:(length(out_list) - 1)){
      if (new_num %in% (apply(combn(out_list,i), FUN = sum, MAR = 2)))
      {
        new_valid <- F
        break
      }
    }

    if (new_valid)
    {
      out_list <- c(out_list, new_num)
    }

  }
  return(out_list)
}

Answer 1

这是个好问题。我对您的原始函数进行了一些更改，使我的运行比您的函数快一点。顺便说一句，你想找多少？

主要思想是我们不应该比绝对必须更频繁地计算更多的东西。我认为 for 循环可能会减慢速度，另外，重复了多少列总和？如果我们可以 "de-dup" 列表，也许我们可以更快地搜索它 [减少、再利用、回收 :)]。

sum_fun2 <- function(k)
{
  out_list <- c(2,3,4) #dummy list
  new_num <- 4 #dummy number
  calc_big_sum <- T #calculate big sum on the first go
  while(length(out_list) < k)
  {
    new_num <- new_num + 1 #dummy number to add

    #calculate big sum, and then find unique values
    if(calc_big_sum){
      big_sum<- unique(unlist(lapply(lapply(2:(length(out_list) - 1), 
                                    FUN = function(x) combn(out_list, m = x)), 
                                    FUN = function(y) apply(y, 2, sum))))
    }

      if(new_num %in% big_sum){
        calc_big_sum = F #don't make it calculate the sum again
      }else{
        out_list <- c(out_list, new_num) #add number to list
        calc_big_sum = T #make it calculate a new sum
      }
  }
  return(out_list)
}

> system.time(sum_fun2(10))
   user  system elapsed 
   0.03    0.00    0.03 
> system.time(sum_fun(10))
   user  system elapsed 
   1.30    0.00    1.27 
> system.time(sum_fun2(14))
   user  system elapsed 
   3.35    0.07    3.47 
> system.time(sum_fun(14))
## I ended it
Timing stopped at: 39.86 0 40.02

r 自身项非和的向量

r vector of non-sums of self items

performance

r

combinatorics