数字的组合以达到给定的总和-R中的递归实现 [英] combinations of numbers to reach a given sum - recursive implementation in R

问题描述

我要做的就是根据给定的解决方案实施

All I want to do is to implement the solution given here (the one in python) in R. I'm not very used to do debugging in R-Studio but even after I have tried that I still can't figure out why my code does not work. Basically (with the example input provided) I get the function to run over all the numbers and then it is stuck in a sort of infinite loop (or function). Can someone please point me in the right direction regarding this?

subset_sum <- function(numbers, target, partial = numeric(0)){
  s <-  sum(partial,na.rm = TRUE)

  # check if the partial sum equals to target
  if (s == target){
    cat("sum(",partial,")","=",target)
  }
  else if (s >= target) {
    return() # if we reach the number why bother to continue

  }
  else {

    for(i in 1:length(numbers)){
      n <-  numbers[i]
      remaining <- numbers[i+1:length(numbers)]
      subset_sum(remaining, target, partial = append(partial,n))
    }
      }
}

subset_sum(c(3,9,8,4,5,7,10),15)

当不在调试模式下运行时，会出现以下错误:

When not run in debug mode it gives me these errors:

Error: node stack overflow
Error during wrapup: node stack overflow

推荐答案

这不是递归函数，但它利用了R处理矩阵/数组类型数据的能力.在#

This is not a recursive function but it takes advantage of R's ability to handle matrix/array type data. Some output is shown after #

v <- c(3,9,8,4,5,7,10)
v <- sort(v)
# [1]  3  4  5  7  8  9 10
target <- 15
# we don't need to check more than at most 4 numbers since 3+4+5+7 (the smallest numbers) is greater than 15
mincombs <- min(which(cumsum(v) > target))  
# [1] 4
Combs <- combn(v, mincombs)  # make combinations of numbers
ans <- mapply(function(x,y) ifelse(y > 0, paste0(paste0(Combs[1:y,x], collapse="+"), "=", target), NA), 1:ncol(Combs), apply(Combs, 2, function(I) which(cumsum(I) == target)))
ans <- unlist(ans[lengths(ans) > 0])
# [1] "3+4+8=15" "3+4+8=15" "3+5+7=15" "3+5+7=15" "3+5+7=15" "7+8=15"

在功能中

myfun <- function(V, target) {
                V <- sort(V)
                mincombs <- min(which(cumsum(V) > target))
                Combs <- combn(V, mincombs)
                ans <- mapply(function(x,y) ifelse(y > 0, paste0(paste0(Combs[1:y,x], collapse="+"), "=", target), NA), 1:ncol(Combs), apply(Combs, 2, function(I) which(cumsum(I) == target)))
                ans <- unlist(ans[lengths(ans) > 0])
                return(ans)
         }

myfun(V = c(3,9,8,4,5,7,10), target = 15)
myfun(V = c(3,9,8,4,5,7,10,12,4,32),target = 20)

这篇关于数字的组合以达到给定的总和-R中的递归实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！