避免expand.grid生成满足和条件的组合，解决R语言整数溢出问题

当pD取值较大（如pD=13）时，原代码通过expand.grid生成所有参数组合再过滤的方式会因组合数量爆炸触发整数溢出。核心需求是直接生成满足以下条件的参数组合：

• 共pD个参数，第1个参数取值范围为0:pD，第i个参数（i≥2）取值范围为0, i, i+1,...,pD
• 所有参数的和 ≤ pD
• 最终组合矩阵需包含额外一列Var0，值为pD - 行和

改进后的代码 #

library(pracma)

# 目标函数
obj_fun <- function(pD, ai_coeffs){
  fun_val <- ai_coeffs[1]
  for (i in 2:pD){
    add_val <- if(ai_coeffs[i] == 0) 0 else nchoosek(ai_coeffs[i], i)/(i^2)
    fun_val <- fun_val + add_val
  }
  return(fun_val)
}

# 递归生成符合条件的参数组合
generate_valid_combs <- function(pD) {
  # 定义每个参数的可选值
  opts <- list()
  opts[[1]] <- 0:pD
  for (i in 2:pD) {
    opts[[i]] <- c(0, i:pD)
  }
  
  # 递归函数：生成前k个参数的组合，且当前和为current_sum
  recurse <- function(k, current_sum, current_comb) {
    if (k > pD) {
      return(list(current_comb))
    }
    # 当前参数的可选值中，满足加上后总和≤pD的部分
    valid_vals <- opts[[k]][opts[[k]] + current_sum <= pD]
    if (length(valid_vals) == 0) {
      return(list())
    }
    # 遍历所有有效值，继续递归
    lapply(valid_vals, function(v) {
      recurse(k + 1, current_sum + v, c(current_comb, v))
    }) %>% unlist(recursive = FALSE)
  }
  
  # 启动递归，从第1个参数开始，当前和为0，当前组合为空
  all_combs <- recurse(1, 0, c())
  # 转换为矩阵
  combs_mat <- do.call(rbind, all_combs)
  colnames(combs_mat) <- paste0("Var", 1:pD)
  # 添加Var0列
  combs_mat <- cbind(Var0 = pD - rowSums(combs_mat), combs_mat)
  return(combs_mat)
}

# 主循环
for (pD in 3:25) {
  cat('pD =', pD, ':\n')
  # 直接生成有效组合
  combs_mat <- generate_valid_combs(pD)
  # 向量化计算目标函数值
  res_vec <- apply(combs_mat, 1, function(row) obj_fun(pD, as.numeric(row)))
  # 输出最优组合
  print(combs_mat[which.max(res_vec), ])
  cat('\n')
}

关键改进说明 #

• 递归生成有效组合：避免先生成所有可能组合再过滤，而是在生成过程中实时检查总和约束，只保留符合条件的分支，大幅减少计算量和内存占用，彻底规避整数溢出。
• 向量化计算优化：用apply替代循环拼接res_vec，提升计算效率。
• 修复原代码bug：原代码中ais_list的循环赋值错误（覆盖了第一个元素），改进后的opts列表正确生成每个参数的可选值。

内容的提问来源于stack exchange，提问作者HeyCool08