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 をつけるとエラーになる