2

我试图检查给定列表是否是另一个列表的子序列：

以下是给出 true 的列表示例：

subseq "" "w"
subseq "w" "w"
subseq "ab" "cab"
subseq "cb" "cab"
subseq "aa" "xaxa"
not (subseq "aa" "xax")
not (subseq "ab" "ba")

我刚来，但在某些情况下它给出了错误的结果

subseq :: Eq a => [a] -> [a] -> Bool
subseq [] [] = True
subseq [] ys = True
subseq xs [] = False
subseq (x:xs) (y:ys) = x == y || subseq xs ( 1 `drop` ys )
4

3 回答 3

7

两件事，一高一低。先说高水平：

您的递归案例不正确。在英语中，您已经写过一个非空列表是另一个非空列表的子序列，如果它们的第一个字符匹配，或者如果列表 1 中除第一个字符之外的每个字符都是第二个列表中除前两个字符之外的每个字符的子序列。这显然是不正确的，因为例如“aaa”不是“abc”的子序列，即使它们的第一个字符匹配，并且“db”不是“cab”的子序列，即使“b”是“b”的子序列.

对于最后一种情况，更好的方法是用英语将其表达为：“一个非空列表是另一个非空列表的子序列，如果： 1. 它们的第一个字符匹配并且列表一的剩余字符是剩余字符的子序列列表 2 或 2。它们的第一个字符不匹配，列表 1 是列表 2 中除第一个之外的所有字符的子序列。”

由于这看起来像家庭作业，我将把它留给您将其翻译成 Haskell 代码。

低级：代码片段

subseq (x:xs) (y:ys) = x == y || subseq xs ( 1 `drop` ys )

不做你认为它做的事。ys已经是第二个列表中除第一个之外的所有元素；您不需要从中删除更多元素。此外，第一种情况 ( subseq [] [] = True) 是不必要的，因为它会被第二种情况捕获，但这没什么大不了的。

于 2012-11-04T16:57:33.533 回答
2

对于任何只是在寻找简单的线性时间实现的人，这里有一个。

subseq :: Eq a => [a] -> [a] -> Bool
[]     `subseq` _      = True
(_:_ ) `subseq` []     = False
(a:as) `subseq` (b:bs) = (if a == b then as else a:as) `subseq` bs
于 2013-04-07T18:13:03.643 回答
1

这样做：

import Control.Monad

subseq a b = elem a . filterM (\x-> [True,False]) $ b

（为此感谢 SO / sacundim！）。

从 jacobm 的回答中得到建议，你会得到

subseq [] ys = True
subseq xs [] = False
subseq (x:xs) (y:ys) = x == y && (....) 
                    || x /= y && subseq (....) (....)

用警卫写得更好，

subseq (x:xs) (y:ys) 
             | x == y    = (....) 
             | otherwise = subseq (....) (....)

第一个代码最好被视为规范，而不是代码，它非常低效。为了改进它，我们可以尝试融合 elem和filterM- 这可能已经实现为

filterM p xs = liftM concat $ sequence [ do {t<-p x; return [x|t]} | x<-xs]

以便

elem xs $ filterM (\x-> [True,False]) ys                               ==
elem xs $ map concat $ sequence [ [[y|t] | t<-[True,False]] | y<-ys]   ==
elem xs $ map concat $ sequence [ [[y],[]] | y<-ys]                    ==

not.null $ filter (match [[x]|x<-xs]) $ sequence [ [[y],[]] | y<-ys]
  where
    match [] _ = True
    match _ [] = False
    match ([x]:t) ([y]:s) | x==y = match t s
    match q       (_:s)          = match q s                           == 

not.null $ [()|r<-sequence [ [[y],[]] | y<-ys], match [[x]|x<-xs] r]   ==

match2 xs ys
  where
    match2 [] _ = True
    match2 _ [] = False
    match2 (x:t) (y:s) | x==y = match2 t s
    match2 q     (_:s)        = match2 q s
于 2012-11-05T09:01:47.843 回答