1

intリストリストの合計を計算するコードを書くのに苦労しています。たとえば、次のリストを検討すると

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

毎回選択する整数に応じて、さまざまな可能な合計を取得できます。

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

誰かが私がそれを解決できる可能性のある方法（コードは必要ありません）を与えることができますか？

4

3 に答える 3

1

これは、リストとパターンマッチングのみを使用して、末尾再帰（ちょっと）バージョンのアルゴリズムを作成するための私の試みです。SMLではなくOCamlで書かれており、内部リストの昇順が必要です

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要約の作成にマップユーティリティを使用しないようにする関数
  • listMergeソートされたリストを整数セットとして使用するためのsetunionに等しい関数
  • listSums合計を2セットのデカルト積にマッピングする関数
  • 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 に答える
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

明らかに、ほとんどの関数は、引数を正しい順序でペアとして受け取るように作成されている可能性があるため、無名関数でラップするのではなく、マップ関数とフォールド関数に直接与えられています。

于 2013-01-29T17:07:25.393 に答える
-2

私は再帰ループでそれを解決しようとします-擬似コードで：

sum = 0;

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

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

  }


}

したがって、配列のすべての配列要素を合計し、その配列の配列内のすべての要素に対してその関数を呼び出す関数内で値を合計する関数を呼び出します。笑

  1. intの配列を受け取り、forまたはwhileループを含むintを追加する関数を作成します。
  2. メイン配列をループし、含まれているすべての配列要素を呼び出して、要素がなくなるまで合計する関数を呼び出します。これは、すべてのスクリプト/プログラミング言語でアクセスできる配列の.lengthを操作することで実現できます。
于 2013-01-29T16:20:04.717 に答える