Longest common subsequence

Longest common subsequence - Rosetta Code を Groovy で実装してみる。
DP は Java 版を再帰は Haskell 版を参考にした。

Dynamic programming

def lcs1(xs, ys) {
  int N = xs.size()
  int M = ys.size()
  int[][] dp = new int[N+1][M+1]
  for (i in 0..<N)
    for (j in 0..<M)
      dp[i+1][j+1] = xs[i] == ys[j] ?
        dp[i][j] + 1 :
        Math.max(dp[i][j+1], dp[i+1][j])

  def sb = new StringBuilder()
  for ((i,j) = [N,M]; i != 0 && j != 0; ) {
    if (dp[i][j] == dp[i-1][j])
      i--
    else if (dp[i][j] == dp[i][j-1])
      j--
    else {
      assert xs[i-1] == ys[j-1]
      sb << xs[i-1]
      i--
      j--
    }
  }

  return sb.reverse().toString()
}

assert "1234"    == lcs1("1234", "1224533324")
assert "tsitest" == lcs1("thisisatest", "testing123testing")

Groovy では for の初期化のところで複数の変数をカンマ区切りで宣言できないのだが多重代入を使えば宣言できることに気づいた*1。

Recursion

longest = { xs, ys ->
  xs.size() > ys.size() ? xs : ys
}

lcs2 = { xs, ys ->
  xs.empty       ? "" :
  ys.empty       ? "" :
  xs[0] == ys[0] ? xs[0] + lcs2(xs.substring(1), ys.substring(1)) :
  longest(lcs2(xs, ys.substring(1)), lcs2(xs.substring(1), ys))
}.memoize()

assert "1234"    == lcs2("1234", "1224533324")
assert "tsitest" == lcs2("thisisatest", "testing123testing")

編集グラフが必要ないなら再帰版の方がわかりやすい。
memoize しておけばオーダーは DP と変わらないだろうし。

Data.Array

Haskell では Data.Array を使って DP 版が実装されていたので Groovy で実装してみる。

Longest common subsequence - Rosetta Code から引用

import Data.Array
 
lcs xs ys = a!(0,0) where
  n = length xs
  m = length ys
  a = array ((0,0),(n,m)) $ l1 ++ l2 ++ l3
  l1 = [((i,m),[]) | i <- [0..n]]
  l2 = [((n,j),[]) | j <- [0..m]]
  l3 = [((i,j), f x y i j) | (x,i) <- zip xs [0..], (y,j) <- zip ys [0..]]
  f x y i j 
    | x == y    = x : a!(i+1,j+1)
    | otherwise = longest (a!(i,j+1)) (a!(i+1,j))

def lcs3(xs, ys) {
  int N = xs.size()
  int M = ys.size()
  def longest = { l1, l2 -> l1.size() > l2.size() ? l1 : l2 }
  def a  = new Closure[N+1][M+1]
  def dp = { i, j -> a[i][j].call() }.memoize()
  for (i in 0..N) a[i][M] = { "" }
  for (j in 0..M) a[N][j] = { "" }
  for (i in 0..<N)
    for (j in 0..<M)
      a[i][j] = xs[i] == ys[j] ?
        { n, m -> xs[n] + dp(n+1,m+1) }.curry(i,j) :
        { n, m -> longest(dp(n,m+1), dp(n+1,m)) }.curry(i,j)
  dp(0,0)
}

assert "1234"    == lcs3("1234", "1224533324")
assert "tsitest" == lcs3("thisisatest", "testing123testing")

i,j を変数のままつかむと値が変わってしまうので部分適用した。

*1:def をつけるとエラーになる