Python-获取列表最长公共子序列的长度

Question

我试图以最简单的方式在LCS中实现，但是我没有得到正确的值。我得到的不是4。我不确定我的代码有什么问题：

X= ['A','B','C','B','D','A','B']
Y= ['B','D','C','A','B','A','X','Y']

m= len(X)
n= len(Y)
c={}
for i in range(1,m) :
    c[i,0]=0

for j in range(0,n):
    c[0,j]=0

for i in range (1,m):
    for j in range (1,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]


print c[m-1,n-1]
print c

Answer 1

看起来你正在使用的索引可能是你问题的根源。如果我理解正确的话，您正在寻找长度为4的LCS'BCBA'，但实际上您从未将第一个条目与任何内容进行比较，因此您没有机会匹配Y的第一个元素'B'

我对你的代码做了一些小小的修改，得到了4个解决方案：

X = ['A', 'B', 'C', 'B', 'D', 'A', 'B']
Y = ['B', 'D', 'C', 'A', 'B', 'A', 'X', 'Y']

m = len(X)
n = len(Y)
c = {}
for i in range(0, m+1):
    c[i, 0] = 0

for j in range(0, n+1):
    c[0, j] = 0

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
        else:
            c[i, j] = max(c[i-1, j],
                          c[i, j-1])
print c[m, n]

希望这有帮助。你知道吗

Answer 2

下面是我用于LCS的实现，它返回(percent_in_common, sequence_in_common)

def longest_common_sequence(a,b):
   from collections import deque

   n1=len(a)
   n2=len(b)
   if not n1:
      if not n2:
         return 100.0, ''
      return 0.0, ''
   if not n2:
      return 0.0, ''
   previous=deque()
   for i in range(n2):
      previous.append((0,''))
   over = (0,'')
   for i in range(n1):
      left = corner = (0,'')
      for j in range(n2):
         over = previous.popleft()
         if a[i] == b[j]:
            this = corner[0] + 1, corner[1]+a[i]
         else:
            this = max(over,left)
         previous.append(this)
         left, corner = this, over
   return round(200.0*this[0]/(n1+n2),2),this[1]