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

Вот реализация я использовал для ЛВПА, он возвращает (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] 

Answer 2

Это выглядит как одна индексации вы используете может быть корень вашей проблемы. Если я правильно понимаю, вы ищете LCS «BCBA» длиной 4, но вы никогда не сравниваете первую запись с чем-либо, поэтому у вас нет возможности сопоставить «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] 

Надеется, что это помогает.