lcs.py

# アルゴリズムイントロダクション 15.4 LCS
def lcs_length(x, y):
    m, n  = len(x), len(y)
    b = [[0 for _ in range(n+1)] for _ in range(m+1)]
    c = [[0 for _ in range(n+1)] for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if x[i-1] == y[j-1]:
                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 lcs_decode(b, X, i, j):
    import collections
    res = collections.deque([])
    while True:
        if i == 0 or j == 0:
            break
        if b[i][j] == '↖':
            res.appendleft(X[i-1])
            i -= 1
            j -= 1
        elif b[i][j] == "↑":
            i -= 1
            continue
        else:
            j -= 1
            continue
    return res

def lcs_decode_negative(b, X, i, j):
    import collections
    res = collections.deque([])
    while True:
        if i == 0 or j == 0:
            break
        if b[i][j] == '↖':
            i -= 1
            j -= 1
        elif b[i][j] == "↑":
            res.appendleft(X[i-1])
            i -= 1
            continue
        else:
            j -= 1
            continue
    if i != 0:
        for i in range(1,i+1):
            res.appendleft(X[i-1])
    return res


dat = []
dat.append("policy-0001")
dat.append("policy-9999")
dat.append("policy-0002")
dat.append("policy-0003")
dat.append("policy-0014")
dat.append("policy-9001")
dat.append("policy-0022")
tobe = sorted(dat)

# current: ['policy-0001', 'policy-9999', 'policy-0002', 'policy-0003', 'policy-0014', 'policy-9001', 'policy-0022']
print("current: {0}".format(dat))
# tobe   : ['policy-0001', 'policy-0002', 'policy-0003', 'policy-0014', 'policy-0022', 'policy-9001', 'policy-9999']
print("tobe   : {0}".format(tobe))

c, b = lcs_length(dat, tobe)

# 共通している順番
# deque(['policy-0001', 'policy-0002', 'policy-0003', 'policy-0014', 'policy-9001'])
print(lcs_decode(b, dat, len(dat) , len(tobe) ))

# 共通していない順番
# deque(['policy-9999', 'policy-0022'])
print(lcs_decode_negative(b, dat, len(dat) , len(tobe) ))