8

最長共通部分列（LCS）を見つける関数を作成しました。たとえば、chars BANANAとATANAの2つのシーケンスの場合、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' ））-> List（'A'、'A'、'N'、'A'）
LCS（Vector（'B'、'A'、'N'、'A'、'N'、'A'）、Vector（'A'、'T'、'A'、'N'、'A' ））-> Vector（'A'、'A'、'N'、'A'）

...他のすべてのSeqについても同様です。

LCSが文字列と配列も処理できれば素晴らしいと思います。

LCS（ "BANANA"、 "ATANA"）-> "AANA"
LCS（Array（'B'、'A'、'N'、'A'、'N'、'A'）、Array（'A'、'T'、'A'、'N'、'A' ））-> Array（'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 に答える