アルゴリズムイントロダクション 2巻 第3版 練習問題15.4-2, 15.4-3, 15.4-4

lcs_length.py

# -*- coding: utf-8 -*-

import codecs
import sys

class Matrix:
    def __init__(self, rows, columns, value=0):
        self.rows = rows
        self.columns = columns
        self.mat = [[value for _ in range(columns)] for _ in range(rows)] 
        return

    def __getitem__(self, pos):
        r, c = pos
        return self.mat[r][c]

    def __setitem__(self, pos, v):
        r,c = pos
        self.mat[r][c] = v
        return

def lcs_length(x, y):
    m = len(x)
    n = len(y)
    b = Matrix(m, n)
    c = Matrix(m+1, n+1)
    for i in range(0, m):
        for j in range(0, n):
            if x[i] == y[j]:
                c[i,j] = c[i-1,j-1] + 1
                b[i,j] = '\\'
            elif c[i-1,j] >= c[i,j-1]:
                c[i,j] = c[i-1,j]
                b[i,j] = '|'
            else:
                c[i,j] = c[i,j-1]
                b[i,j] = '-'
    return (c,b)

def print_lcs(b, x, i, j):
    if i < 0 or j < 0:
        return
    if b[i,j] == '\\':
        print_lcs(b, x, i-1, j-1)
        print x[i], i, j
    elif b[i,j] == '|':
        print_lcs(b, x, i-1, j)
    else:
        print_lcs(b, x, i, j-1)
    return
#
# Exercise 15.4-2
#
def lcs_length_2(x, y):
    m = len(x)
    n = len(y)
    c = Matrix(m+1, n+1)
    for i in range(0, m):
        for j in range(0, n):
            if x[i] == y[j]:
                c[i,j] = c[i-1,j-1] + 1
            elif c[i-1,j] >= c[i,j-1]:
                c[i,j] = c[i-1,j]
            else:
                c[i,j] = c[i,j-1]
    return c

def print_lcs_2(c, x, y, i, j):
    if i < 0 or j < 0:
        return
    if x[i] == y[j]:
        print_lcs_2(c, x, y, i-1, j-1)
        print x[i], i, j
    elif c[i,j] == c[i-1,j]:
        print_lcs_2(c, x, y, i-1, j)
    else:
        print_lcs_2(c, x, y, i, j-1)
    return

#
# Exercise 15.4-3 (top down algorithm with memoization)
#
def lcs_length_3(x, y):
    m = len(x)
    n = len(y)
    c = Matrix(m+1, n+1, 9)
    lookup_lcs(x, y, m-1, n-1, c)
    return c

def lookup_lcs(x, y, m, n, c):
    if c[m,n] == 9:
        if m < 0 or n < 0:
            c[m,n] = 0
        elif x[m] == y[n]:
            c[m,n] = lookup_lcs(x, y, m-1, n-1, c) + 1
        else:
            lcs1 = lookup_lcs(x, y, m-1, n, c)
            lcs2 = lookup_lcs(x, y, m, n-1, c)
            if lcs1 >= lcs2:
                c[m,n] = lcs1
            else:
                c[m,n] = lcs2
    return c[m,n]

#
# Exercise 15.4-4
#

# Space = 2 * min(m,n) + O(1)
def lcs_length_4_1(x, y):
    m = len(x)
    n = len(y)    
    if m <= n:
        s, l, o, p = x, y, m, n
    else:
        s, l, o, p = y, x, n, m
    c1 = [0] * (o+1)
    c2 = [0] * (o+1)
    for j in range(0, p):
        for i in range(0, o):
            if s[i] == l[j]:
                c2[i] = c1[i-1] + 1
            elif c2[i-1] >= c1[i]:
                c2[i] = c2[i-1]
            else:
                c2[i] = c1[i]
        for i in range(0, o):
            c1[i] = c2[i]
    print c2[o-1]
    return

# Space = min(m,n) + O(1) 
def lcs_length_4_2(x, y):
    m = len(x)
    n = len(y)    
    if m <= n:
        s, l, o, p = x, y, m, n
    else:
        s, l, o, p = y, x, n, m
    c = [0] * (o+1)
    for j in range(0, p):
        old = 0
        for i in range(0, o):
            if s[i] == l[j]:
                new = old + 1
            elif c[i-1] >= c[i]:
                new = c[i-1]
            else:
                new = c[i]
            old = c[i]
            c[i] = new
    print c[o-1]
    return

def main(args):
    sys.stdin  = codecs.getreader('utf_8')(sys.stdin)
    sys.stdout = codecs.getwriter('utf_8')(sys.stdout)
    x = args[0]
    y = args[1]
    print 'Text'
    c,b = lcs_length(x, y)
    print_lcs(b, x, len(x)-1, len(y)-1)
    #"""
    print ""
    print "  ", (("  %s" * len(y)) % tuple([j for j in range(0, len(y))]))
    print "  ", (("  %s" * len(y)) % tuple([j for j in y]))
    for i in range(0, len(x)):
        print i, x[i], c.mat[i][0:-1]
    print ""
    for i in range(0, len(x)):
        print i, x[i], b.mat[i]
    print ""
    #"""

    print 'Exercise 15.4-2'
    c1 = lcs_length_2(x, y)
    print_lcs_2(c1, x, y, len(x)-1, len(y)-1)
    #"""
    print ""
    print "  ", (("  %s" * len(y)) % tuple([j for j in range(0, len(y))]))
    print "  ", (("  %s" * len(y)) % tuple([j for j in y]))
    for i in range(0, len(x)):
        print i, x[i], c1.mat[i][0:-1]
    print ""
    #"""

    print 'Exercise 15.4-3'
    c2 = lcs_length_3(x, y)
    print_lcs_2(c2, x, y, len(x)-1, len(y)-1)
    #"""
    print ""
    print "  ", (("  %s" * len(y)) % tuple([j for j in range(0, len(y))]))
    print "  ", (("  %s" * len(y)) % tuple([j for j in y]))
    for i in range(0, len(x)):
        print i, x[i], c1.mat[i][0:-1]
    print ""
    #"""

    print 'Exercise 15.4-4 #1'
    lcs_length_4_1(x, y)
    print ""

    print 'Exercise 15.4-4 #2'
    lcs_length_4_2(x, y)

    return

if __name__ == '__main__':
    sys.exit(main(sys.argv[1:]))