时间戳

首页 > 解决方案 > 在 Haskell 中过滤具有相同数量的不同元素的列表

list - 在 Haskell 中过滤具有相同数量的不同元素的列表

问题描述

我对 Haskell 很陌生，我有数据data Instruction = Add | Sub | Mul | Div | Dup | Pop deriving (Eq,Ord,Show,Generic)，我正在生成包含大小为 n的所有可能组合Mul的列表。DupmapM (const [Mul, Dup]) [1..n])

我只想要以开头Dup和结尾的列表，Mul所以我使用了filter((== Mul) . last)(filter((== Dup) . head) (mapM (const [Mul, Dup]) [1..n]))，但我也只想要其中具有相同数量Mul和的列表，Dup但我似乎无法想出一种方法来做到这一点。我该如何过滤它，是否有更有效的方法来做到这一点，因为随着列表变得越来越大，可能会有大量的组合？

示例列表如下所示：对于大小为 4 的列表[Dup,Mul,Dup,Mul]。[Dup,Dup,Mul,Mul]

标签： listhaskellfilter

解决方案

虽然您的方法是正确的，但我认为这不是最有效的方法。您生成2^N列表，然后过滤掉其中的许多。忘记保持计数简单的其他要求，通过要求我们有与Muls一样多的Dups，我们最终只得到列表（大小为choose(N, N/2)的子集的数量），这是一个小得多的数字。N/21..N

相反，我们可以尝试避免过滤并首先生成想要的列表。我建议采用以下方法，您可以根据需要对其进行修改以满足其他要求。

我们定义了一个函数sameMulDup，它接受两个整数m并d生成所有带有m Muls 和d Dups 的列表。

sameMulDup :: Int -> Int -> [[Instruction]]
sameMulDup 0 d = [replicate d Dup]
sameMulDup m 0 = [replicate d Mul]
sameMulDup m d = do
    -- generate the first element
    x <- [Dup, Mul]
    -- compute how many m and d we have left
    let (m', d') = case x of
           Dup -> (m  , d-1)
           Mul -> (m-1, d  )
    -- generate the other elements
    xs <- sameMulDup m' d'
    return (x:xs)

直观地说，如果d=0或者m=0只有一个可能的列表包含在 out list-of-lists 结果中。否则，我们不确定地选择第一个元素，递减相应的计数器dor m，然后生成其余的。

或者，最后一个等式可以替换为以下更基本的等式：

sameMulDup m d =
    map (Dup:) (sameMulDup m (d-1))
    ++
    map (Mul:) (sameMulDup (m-1) d)

无论如何，给定sameMuldup，您应该能够解决您的全部任务。

推荐阅读