4

我一直在为看起来像一个简单算法的东西而苦苦挣扎，但到目前为止还找不到一种干净的方式来以函数式风格表达它。这是问题的概要：假设我有 2 个数组 X 和 Y，

X = [| 1; 2; 2; 3; 3 |]
Y = [| 5; 4; 4; 3; 2; 2 |]

我想要的是检索匹配的元素和不匹配的元素，例如：

matched = [| 2; 2; 3 |]
unmatched = [| 1; 3 |], [| 4; 4; 5 |]

在伪代码中，这就是我解决问题的方式：

let rec match matches x y =
    let m = find first match from x in y
    if no match, (matches, x, y)
    else
        let x' = remove m from x
        let y' = remove m from y
        let matches' = add m to matches
        match matches' x' y'

我遇到的问题是"remove m from x"部分 - 我找不到一个干净的方法来做到这一点（我有工作代码，但它很难看）。是否有一种很好的、​​惯用的函数式方法来解决该问题，无论是删除部分，还是编写算法本身的不同方法？

4

2 回答 2

4

这可以使用正确的数据结构轻松解决，但如果您想手动完成，这就是我在 Haskell 中的做法。我不太了解 F# 来翻译这个，但我希望它足够相似。所以，在这里，在（半）识字的 Haskell 中。

overlap xs ys =

我首先对这两个序列进行排序，以摆脱必须了解先前值的问题。

  go (sort xs) (sort ys)
    where

递归的两种基本情况很容易处理——如果其中一个列表为空，则结果将另一个列表包含在不重叠的元素列表中。

      go xs []           = ([], (xs, []))
      go [] ys           = ([], ([], ys))

然后我检查每个列表中的第一个元素。如果它们匹配，我可以确定列表在该元素上重叠，因此我将其添加到包含的元素中，并让排除的元素保留。我通过在列表的尾部递归来继续搜索列表的其余部分。

      go (x:xs) (y:ys)
        | x == y = let (  included, excluded)     = go xs ys
                   in  (x:included, excluded)

然后是有趣的部分！我本质上想知道的是其中一个列表的第一个元素是否不存在于第二个列表中——在这种情况下，我应该将它添加到排除列表中，然后继续搜索。

        | x < y  = let (included, (  xex,   yex)) = go xs (y:ys)
                   in  (included, (x:xex,   yex))
        | y < x  = let (included, (  xex,   yex)) = go (x:xs) ys
                   in  (included, (  xex, y:yex))

这实际上就是它。它似乎至少适用于您给出的示例。

> let (matched, unmatched) = overlap x y
> matched
[2,2,3]
> unmatched
([1,3],[4,4,5])
于 2013-06-07T23:40:11.227 回答
3

您似乎在描述多重集（包）及其操作。

如果使用合适的数据结构，操作很容易实现：

// Assume that X, Y are initialized bags
let matches = X.IntersectWith(Y)
let x = X.Difference(Y)
let y = Y.Difference(X)

.NET 框架中没有内置的 Bag 集合。您可以使用 Power Collection 库，包括采用上述函数签名的Bag 类。

更新：

你可以用一个弱升序列表来表示一个包。这是@kqr 的 F# 语法答案的改进版本：

let overlap xs ys =
    let rec loop (matches, ins, outs) xs ys =
        match xs, ys with
        // found a match
        | x::xs', y::ys' when x = y -> loop (x::matches, ins, outs) xs' ys'
        // `x` is smaller than every element in `ys`, put `x` into `ins`
        | x::xs', y::ys' when x < y -> loop (matches, x::ins, outs) xs' ys
        // `y` is smaller than every element in `xs`, put `y` into `outs`
        | x::xs', y::ys' -> loop (matches, ins, y::outs) xs ys'
        // copy remaining elements in `xs` to `ins`
        | x::xs', [] -> loop (matches, x::ins, outs) xs' ys
        // copy remaining elements in `ys` to `outs`
        | [], y::ys' -> loop (matches, ins, y::outs) xs ys'
        | [], [] -> (List.rev matches, List.rev ins, List.rev outs)
    loop ([], [], []) (List.sort xs) (List.sort ys)

在两次调用 （List.sort可能是）之后O(nlogn)，查找匹配项与两个列表的长度之和呈线性关系。

如果您需要一个快速又脏的包模块，我建议使用这样的模块签名：

type Bag<'T> = Bag of 'T list

module Bag =
    val count : 'T -> Bag<'T> -> int
    val insert : 'T -> Bag<'T> -> Bag<'T>
    val intersect : Bag<'T> -> Bag<'T> -> Bag<'T>
    val union : Bag<'T> -> Bag<'T> -> Bag<'T>
    val difference : Bag<'T> -> Bag<'T> -> Bag<'T>
于 2013-06-07T23:31:11.723 回答