algorithm - 根据匹配规则按连续对过滤数组或列表

Question

这可能是微不足道的，我确实有一个解决方案，但我对此并不满意。不知何故，(很多)更简单的形式似乎不起作用，并且它在拐角处变得困惑(连续的第一个或最后一个匹配对)。

为简单起见，我们将匹配规则定义为任何两个或多个相差为 2 的数字。示例:

> filterTwins [1; 2; 4; 6; 8; 10; 15; 17]
验证它:int list = [2; 4; 6; 8; 10; 15; 17]

我目前使用的代码是这样的，只是感觉草率和超重:

let filterTwins list =
    let func item acc =
        let prevItem, resultList = acc
        match prevItem, resultList with
        | 0, [] 
            -> item, []
        | var, [] when var - 2 = item
            -> item, item::var::resultList
        | var, hd::tl when var - 2 = item && hd <> var
            -> item, item::var::resultList
        | var, _ when var - 2 = item
            -> item, item::resultList
        | _ 
            -> item, resultList

    List.foldBack func list (0, [])
    |> snd

我打算用我自己的原始练习来试验 List.foldBack、大型列表和并行编程(进展顺利)但最终搞砸了“简单”的部分...

指导回答

• Daniel's last , 113 个字符*, 容易理解, 慢
• Kvb's 2nd , 106 个字符*(如果我包含该函数)，简单，但返回值需要工作
• Stephen's 2nd , 397 个字符*，冗长且相对复杂，但速度最快
• Abel's , 155 个字符*，基于 Daniel's，允许重复(顺便说一句，这不是必需的)并且速度相对较快。

有更多的答案，但我相信以上是最明显的。希望我接受丹尼尔的答案作为解决方案不会伤害任何人的感情:每一个解决方案都应该成为选定的答案(!)。

* 将函数名称作为一个字符进行计数

Answer 1

这会如你所愿吗？

let filterTwins l = 
    let rec filter l acc flag =
        match l with
        | [] -> List.rev acc
        | a :: b :: rest when b - 2 = a -> 
            filter (b::rest) (if flag then b::acc else b::a::acc) true
        | _ :: t -> filter t acc false
    filter l [] false

这是非常低效的，但这里有另一种使用更多内置函数的方法:

let filterTwinsSimple l =
    l 
    |> Seq.pairwise 
    |> Seq.filter (fun (a, b) -> b - 2 = a)
    |> Seq.collect (fun (a, b) -> [a; b])
    |> Seq.distinct
    |> Seq.toList

也许稍微好一点:

let filterTwinsSimple l =
    seq { 
        for (a, b) in Seq.pairwise l do
            if b - 2 = a then 
                yield a
                yield b 
    }
    |> Seq.distinct
    |> Seq.toList