2

我正在尝试用蛮力方法解决最大子数组问题，即生成所有可能的子数组组合。我得到了一些有用的东西，但它根本不令人满意，因为它产生了太多重复的子数组。

有谁知道用最少数量的重复元素生成所有子数组（以 [[]] 形式）的聪明方法？

顺便说一句，我是 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 专家，但我偶尔会玩弄它，发现解决这样的问题是一种有趣的分心，并且喜欢弄清楚它为什么有效。希望下面的解释会有所帮助:)

dave4420 的答案（您的答案没有）的关键属性是该对(startPos, endPos)对于它生成的每个子数组都是唯一的。现在，观察两个子数组如果它们的or不同，则它们是不同的。应用于原始数组会返回一个子数组列表，每个子数组都有唯一的，并且相同（等于数组中的元素数）。依次应用于这些子数组中的每一个会产生另一个子数组列表——每个输入子数组输出一个子数组列表。请注意，这不会干扰输入子数组之间的区别，因为通过调用单个输入子数组输出的子数组都保持相同startPosendPosinitsstartPosendPostailstails tailsstartPos：也就是说，如果您有两个具有不同startPoses 的子数组，并将它们都放入tails，则从第一个输入子数组生成的每个子数组都将不同于从第二个输入子数组生成的每个子数组。

tails此外，在单个子数组上调用 产生的每个子数组都是不同的，因为尽管它们都共享相同的startPos，但它们都有不同的endPoses。因此，由 产生的所有子阵列(concatMap tails) . inits都是不同的。只需要注意没有遗漏任何子数组：对于从 position 开始并在 positioni结束的任何子数组j，该子数组必须显示为j-i+1通过应用于tails生成的i+1第 th 列表而生成的第 th 列表inits。所以总而言之，每个可能的子数组只出现一次！

于 2012-09-14T13:01:53.973 回答