1

我正在努力编写代码，它将计算 int list list 的总和。例如，如果我们考虑以下列表

[[1],[1,5],[7],[2,3,4]]

我们可以得到不同的可能总和，具体取决于我们每次选择的整数：

[11,12,13,15,16,17]

有人可以提供可能的方法（不需要代码）我可以解决它吗？

4

3 回答 3

1

以下是尝试将步骤分解为可读且希望可以理解的部分

fun sums xss =
    let
      fun extend xss y = map (fn xs => y :: xs) xss
      fun extend' xss ys = foldl (fn (y, b) => extend xss y @ b) [] ys
      fun extend'' xss = foldl (fn (xs,b) => extend' b xs) [[]] xss
      fun sum xs = foldl op+ 0 xs
    in
      map sum (extend'' xss)
    end


- sums [[1],[1,5],[7],[2,3,4]];
val it = [17,13,16,12,15,11] : int list

显然，大多数函数都可以按照正确的顺序将参数作为对，因此直接提供给 map 和 fold 函数，而不是将它们包装在匿名函数中。

于 2013-01-29T17:07:25.393 回答
1

这是我尝试仅使用列表和模式匹配来制作尾递归（有点）版本的算法。它是用 OCaml 而不是 SML 编写的，并且需要内部列表的升序

let reverse list = 
    let rec iter list acc :int list = match list with
    [] -> acc
    | x::xs -> iter xs (x::acc)
 in iter list [];;

let listAdd num list = 
  let rec iter num list acc :int list = match list with
     [] -> acc
    | x::xs -> iter num xs ((x + num)::acc)
  in reverse( iter num list []);;   

let listMerge listX listY = 
  let rec iter listX listY acc : int list = match listX with 
     [] -> (reverse acc) @ listY
     | x :: xs -> match listY with 
        [] -> (reverse acc ) @ listX
        | y :: ys -> match ( compare x y ) with
           0  ->  iter xs ys ( x::acc )
          |(-1) ->  iter xs listY ( x::acc )    
          | 1 ->  iter listX ys ( y::acc )
  in iter listX listY [];;  

let listSums listX listY =
 let rec iter listX listY acc = match listX with 
   [] -> acc
   | x :: xs -> iter xs listY ( listMerge acc (listAdd x listY ) )
 in iter listX listY [];;  

let possibleSums shallowList = match shallowList with 
   [] -> []
   | headList :: lists -> 
      let rec iter acc lists  = match lists with 
          [] -> acc
          | headList :: other -> iter ( listSums acc headList ) other  
      in iter headList lists;;

这里 possibleSums [[1];[1;5];[7];[2;3;4]];;评估为int list = [11; 12; 13; 15; 16; 17]

所以基本上合乎逻辑的步骤是：

  • 该reverse函数只是在构建结果累加器后恢复顺序的实用程序 - 尾递归优化的常用概念
  • listAdd在构建摘要时避免使用 map 实用程序的功能
  • listMerge等于 set union的函数将排序列表用作整数集
  • listSums将求和映射到两组笛卡尔积的函数
  • 将总和映射到所有集合的完整笛卡尔积的最终级别的posibleSums函数。

该算法不仅通过TCO避免了递归中的堆栈溢出，而且还为这个计算问题提供了接近最优的解决方案。

此外，可以通过添加过早的合并排序和从集合中删除重复元素来进一步改进此解决方案，因此内部集合顺序现在无关紧要：

let split lst = 
    let rec iter lst partX partY = match lst with
        [] -> partX,partY
        | x::xs -> iter xs partY (x::partX)
    in iter lst [] [];;

let rec mergeSort lst = match lst with 
    [] -> []
    |[x] -> [x]
    | _ -> let partX,partY = split lst in
           listMerge (mergeSort partX) (mergeSort partY);;

let possibleSums shallowList = match shallowList with 
   [] -> []
   | headList :: lists -> 
      let rec iter acc lists  = match lists with 
          [] -> acc
          | headList :: other -> iter ( listSums acc (mergeSort headList) ) other  
      in iter (mergeSort headList) lists;;

您可以通过简单的示例测试其效率。让我们定义用于制作重复列表的重复函数：

 let rec repeat elem n = match n with
     0 -> []
    | _ -> elem :: (repeat elem (n - 1));;

在这种情况下，possibleSums( repeat( repeat 1 30) 30 )将立即计算正确的单例答案 int list = [30]。虽然更直接的解决方案（如 Jesper 的解决方案）将永远做到这一点。

于 2013-01-29T19:03:58.100 回答
-2

我会尝试用递归循环来解决它 - 在伪代码中：

sum = 0;

while (i < arrayOfArrays.length ) {
     sumUp(arrayOfArrayElements);
     i ++
 }

 function sumUp() {
     while( j < arrayOfArrayElement.length){
     sum = sum + arrayOfArrayElement[j].val
     j ++

  }


}

因此，您调用一个函数，该函数对数组的每个数组元素求和，并在一个函数内将这些值相加，该函数为该数组数组中的每个元素调用该函数。大声笑

  1. 创建一个函数，该函数接受一个整数数组并使用 for 或 while 循环添加包含的整数。
  2. 循环遍历主数组并调用每个包含数组元素的函数来求和，直到没有更多元素为止，您可以通过使用数组的 .length 来实现这一点，该数组应该可以在每种脚本/编程语言中访问
于 2013-01-29T16:20:04.717 回答