2

I am trying to solve the maximum sub array problem with a brute force approach i.e generating all the possible subarrays combinations. I got something that works but it's not satisfying at all because it produces way too many duplicated subarrays.

Does anyone knows a smart way to generate all the subarrays (in [[]] form) with a minimal number of duplicated elements ?

ちなみにHaskell初心者です。これが私の現在の解決策です：

import qualified Data.List as L

maximumSubList::[Integer]->[Integer]
maximumSubList x = head $ L.sortBy (\a b -> compare (sum b) (sum a)) $ L.nub $ slice x
     where 
        -- slice will return all the "sub lists"
        slice [] = []
        slice x = (slice $ tail x) ++ (sliceLeft x) ++ (sliceRight x)

        -- Create sub lists by removing "left" part
        -- ex [1,2,3] -> [[1,2,3],[2,3],[3]]
        sliceRight [] = []
        sliceRight x = x : (sliceRight $ tail x)

        -- Create sub lists by removing "right" part
        -- ex [1,2,3] -> [[1,2,3],[1,2],[1]]
        sliceLeft [] = []
        sliceLeft x = x : (sliceLeft $ init x)
4

2 に答える 2

6

標準のData.Listモジュールのリストを操作するための多くの便利な関数があります。

import Data.List

slice :: [a] -> [[a]]
slice = filter (not . null) . concatMap tails . inits
于 2012-09-14T12:16:21.610 に答える
3

dave4420 の答えは、スマートで簡潔な Haskell を使用してやりたいことを行う方法です。私は Haskell の専門家ではありませんが、ときどき Haskell をいじって、このような問題を解決するのは興味深い気晴らしであり、なぜそれが機能するのかを正確に理解することを楽しんでいます。うまくいけば、次の説明が役に立ちます:)

dave4420 の答え (あなたの答えにはありません) の重要な特性は、ペア(startPos, endPos)が生成する各サブアレイに対して一意であることです。ここで、またはstartPosが異なる場合、2 つの部分配列が異なることに注意してendPosください。元の配列に適用するinitsと、それぞれが一意startPosで、同じendPos(配列内の要素の数に等しい) を持つ部分配列のリストが返されます。これらのサブ配列のそれぞれに順番に適用するtailsと、サブ配列の別のリストが生成されます。サブ配列の 1 つのリストは、入力サブ配列ごとに出力されます。単一の入力サブ配列で呼び出すことによって出力されるサブ配列はすべて同じ値を保持するため、tails 入力サブ配列間の明確性が妨げられないことに注意してください。tailsstartPos: つまり、異なるstartPoses を持つ 2 つのサブ配列があり、それらの両方を に通すtailsと、最初の入力サブ配列から生成された各サブ配列は、2 番目の入力サブ配列から生成された各サブ配列とは異なります。

tailsさらに、単一のサブ配列に対するの呼び出しによって生成された各サブ配列は、すべて同じstartPosを共有していますが、すべてが異なるendPoses を持っているため、別個のものです。したがって、 によって生成されるすべての部分配列(concatMap tails) . initsは異なります。サブ配列が見逃されないことに注意するだけです: position で開始し、 positioniで終了するサブ配列の場合、そのサブ配列は、 によって生成されたth リストに適用することによって生成されたth リストjとして表示される必要があります。結論として、すべての可能な部分配列は正確に 1 回出現します!j-i+1tailsi+1inits

于 2012-09-14T13:01:53.973 に答える