时间戳

首页 > 解决方案 > Haskell - 将列表拆分为两个总和最接近的子列表

list - Haskell - 将列表拆分为两个总和最接近的子列表

问题描述

我是一名 Haskell 初学者，试图通过解决一些在线测验/问题集来了解有关该语言的更多信息。

问题/问题相当冗长，但其中一部分需要代码来找到将给定列表分成两个（几乎）相等（按总和）子列表的数字。

给定[1..10]

答案应该是7因为1+2+..7 = 28&8+9+10 = 27

这是我实现它的方式

-- partitions list by y
partishner :: (Floating a) => Int -> [a] -> [[[a]]]
partishner 0 xs = [[xs],[]]
partishner y xs = [take y xs : [drop y xs]] ++ partishner (y - 1) xs


-- finds the equal sum
findTheEquilizer :: (Ord a, Floating a) => [a] -> [[a]]
findTheEquilizer xs = fst $ minimumBy (comparing snd) zipParty
  where party = (tail . init) (partishner (length xs) xs) -- removes [xs,[]] types
        afterParty = (map (\[x, y] -> (x - y) ** 2) . init . map (map sum)) party
        zipParty = zip party afterParty -- zips partitions and squared diff betn their sums

给定(last . head) (findTheEquilizer [1..10]) 输出：7

对于附近的数字50k，它工作正常

λ> (last . head) (findTheEquilizer [1..10000])                                                   
   7071.0

当我放入列表中的元素不超过70k元素时，麻烦就开始了。计算需要很长时间。

那么我必须更改代码以使其更好地运行，还是必须更改整个方法？我猜是后者，但我不知道该怎么做。

标签： listhaskelloptimization

解决方案

在我看来，实施相当混乱。例如partishner，似乎构造了一个列表列表的列表a，其中，如果我理解正确，外部列表包含每两个元素的列表：“左侧”的元素列表和“右侧”的元素列表”。因此，这将花费O(n 2 )来构建列表。

通过在 2 元组上使用列表，这也是相当“不安全”的，因为列表可以——尽管这里可能不可能——不包含任何元素、一个元素或两个以上的元素。如果您在其中一个功能中犯了错误，则很难找出该错误。

在我看来，实现“扫描算法”可能更容易：我们首先计算列表中所有元素的总和。这是“右侧”的值，如果我们决定在该特定点拆分，接下来我们开始从左到右移动，每次从右侧的总和中减去元素，并将其添加到左侧的总和中. 我们每次都可以评估分数的差异，例如：

import Data.List(unfoldr)

sweep :: Num a => [a] -> [(Int, a, [a])]
sweep lst = x0 : unfoldr f x0
    where x0 = (0, sum lst, lst)
          f (_, _, []) = Nothing
          f (i, r, (x: xs)) = Just (l, l)
              where l = (i+1, r-2*x, xs)

例如：

Prelude Data.List> sweep [1,4,2,5]
[(0,12,[1,4,2,5]),(1,10,[4,2,5]),(2,2,[2,5]),(3,-2,[5]),(4,-12,[])]

所以如果我们选择在第一个分裂点（第一个元素之前）进行分裂，右边的12和高于左边的和，如果我们在第一个元素之后分裂，右边的和（11）10高于左边的总和（1）。

然后，我们可以通过以下方式获得这些拆分中的最小值minimumBy :: (a -> a -> Ordering) -> [a] -> a：

import Data.List(minimumBy)
import Data.Ord(comparing)

findTheEquilizer :: (Ord a, Num a) => [a] -> ([a], [a])
findTheEquilizer lst = (take idx lst, tl)
    where (idx, _, tl) = minimumBy (comparing (abs . \(_, x, _) -> x)) (sweep lst)

然后我们获得正确的值[1..10]：

Prelude Data.List Data.Ord Data.List> findTheEquilizer [1..10]
([1,2,3,4,5,6,7],[8,9,10])

或 70'000：

Prelude Data.List Data.Ord Data.List> head (snd (findTheEquilizer [1..70000]))
49498

以上并不理想，它可以更优雅地实现，但我将其留作练习。

推荐阅读