8

我编写了查找最长公共子序列（LCS）的函数。例如，对于两个字符序列 BANANA 和 ATANA，它返回 AANA。实现是递归算法的幼稚低效适应，但这与这个问题的目的无关。

def LCS[T](a: Seq[T], b: Seq[T]): Seq[T] = {
    if (a.isEmpty || b.isEmpty)
      Seq.empty
    else if (a.head == b.head)
      a.head +: LCS(a.tail, b.tail)
    else {
      val case1 = LCS(a.tail, b)
      val case2 = LCS(a, b.tail)
      if (case1.length > case2.length) case1 else case2
    }
}

我想以最通用的方式重构这个函数。当前实现适用于任何类型的输入序列，但总是返回 List[T] 类型的集合。我想实现以下行为：

LCS(List('B','A','N','A','N','A'), List('A','T','A','N','A' )) -> 列表('A','A','N','A')
LCS(向量('B','A','N','A','N','A'),向量('A','T','A','N','A' )) -> 向量('A','A','N','A')
...对于所有其他Seq s

以此类推...

如果 LCS 也能处理String和Array那就太好了：

LCS（“香蕉”，“ATANA”）->“AANA”
LCS(数组('B','A','N','A','N','A'),数组('A','T','A','N','A' )) -> 数组('A','A','N','A')

我相信在 Scala 2.8 通用集合库的帮助下，至少可以实现第一个要求。会很高兴看到“重型”机器，例如高级多态性、类型类、CanBuildFrom 等。

谢谢！

4

2 回答 2

6

为了清除我的评论，这就是你要做的（没有给出解释——为此，请参阅这个问题的答案）。

def LCS[A,C](a: C, b: C)(
  implicit c2i: C => Iterable[A], cbf: collection.generic.CanBuildFrom[C,A,C]
): C = {
  val builder = cbf()
  def ListLCS(a: Iterable[A], b: Iterable[A]): List[A] = {
    if (a.isEmpty || b.isEmpty) Nil
    else if (a.head==b.head) a.head :: ListLCS(a.tail,b)
    else {
      val case1 = ListLCS(a.tail, b)
      val case2 = ListLCS(a, b.tail)
      if (case1.length > case2.length) case1 else case2
    }
  }
  builder ++= ListLCS( c2i(a), c2i(b) )
  builder.result()
}

可以直接在内部函数内部使用构建器，但您必须重新设计算法；实际上，您将项目添加到列表的头部，而构建器添加到列表的末尾。因此，为了保持相同的算法，我们制作了一个列表作为中间体。

于 2011-04-20T18:01:32.757 回答
2

替换Seq.empty为a.companion.empty我提供了具有此行为的功能：

scala> LCS(Vector(1, 2, 1, 2, 3), Vector(1, 1, 3))
res3: Seq[Int] = Vector(1, 1, 3)

scala> LCS(List(1, 2, 1, 2, 3), List(1, 1, 3))
res4: Seq[Int] = List(1, 1, 3)

scala> LCS("BANANA", "ANA")                       
res5: Seq[Char] = Vector(A, N, A)

scala> LCS(Array(1, 2, 1, 2, 3), Array(1, 1, 3))
res6: Seq[Int] = ArrayBuffer(1, 1, 3)
于 2011-04-20T17:26:31.480 回答