嗨，我正在解決這個問題，我必須回傳最長公共子序列（lcs）的長度，并且我能夠形成一個執行相同操作的遞回函式，但現在我想知道如何讓這個函式回傳 lcs 是什么。例如
seq1 = 'serendipitous'
seq2 = 'precipitation'
lcs of seq1 and seq2 is - reipito
我想制作一個回傳“reipito”的函式
我寫的回傳 lcs 長度的函式是
def lcs_recursive(seq1, seq2, idx1 = 0, idx2 = 0):
if idx1 == len(seq1) or idx2 == len(seq2):
return 0
if seq1[idx1] == seq2[idx2]:
return 1 lcs_recursive(seq1, seq2, idx1 1, idx2 1)
else:
option1 = lcs_recursive(seq1, seq2, idx1 1, idx2)
option2 = lcs_recursive(seq1, seq2, idx1, idx2 1)
return max(option1, option2)
此函式回傳長度如何 lcs
我厭倦了這樣做但失敗了。請幫忙
uj5u.com熱心網友回復：
轉換發布的代碼以回傳 LCS 而不是長度。
def lcs_recursive(seq1, seq2, idx1 = 0, idx2 = 0):
if idx1 == len(seq1) or idx2 == len(seq2):
return ""
if seq1[idx1] == seq2[idx2]:
return seq1[idx1] lcs_recursive(seq1, seq2, idx1 1, idx2 1)
else:
option1 = lcs_recursive(seq1, seq2, idx1 1, idx2)
option2 = lcs_recursive(seq1, seq2, idx1, idx2 1)
return max(option1, option2, key = len)
測驗
seq1 = 'serendipitous'
seq2 = 'precipitation'
print(lcs_recursive(seq1, seq2))
# Output: 'reipito'
uj5u.com熱心網友回復：
對您的代碼進行最少的更改：
def lcs_recursive(seq1, seq2, idx1 = 0, idx2 = 0, lcs = ''):
if idx1 == len(seq1) or idx2 == len(seq2):
return lcs
if seq1[idx1] == seq2[idx2]:
return lcs_recursive(seq1, seq2, idx1 1, idx2 1, lcs seq1[idx1])
else:
option1 = lcs_recursive(seq1, seq2, idx1 1, idx2, lcs)
option2 = lcs_recursive(seq1, seq2, idx1, idx2 1, lcs)
return max(option1, option2, key=len)
seq1 = 'serendipitous'
seq2 = 'precipitation'
print(lcs_recursive(seq1, seq2)) # reipito
由于您可能lcs_recursive多次functools.cache使用相同的索引對進行呼叫，因此如果使用 Python >= 3.9 或functools.lru_cache使用 Python >= 3.2 可能會提高性能。
例如， ifseq1 = 'ab'和seq2 = 'bd',lcs_recursive('ab', 'bd')最終會呼叫lcs_recursive('ab', 'bd', 2, 1)兩次（您可以通過print(idx1, idx2)在函式中執行第一件事來看到這一點）。通過@lru_cache下面的優化，在第一次呼叫(idx1=2, idx2=1)(ie lcs_recursive('ab', 'bd', 2, 1)) 時，(idx1=2, idx2=1)計算并存盤對應于的結果（在快取中，您可以將其視為字典）。在對同一索引對 ( (idx1=2, idx2=1)) 的后續呼叫中，將查找存盤的結果，以便不必重新計算它。一般來說，lru_cache會根據輸入記憶結果。這就是為什么在下面的代碼中，該函式helper只需要idx1和idx2- 使其更容易lru_cache正常作業。
from functools import lru_cache
def lcs_recursive(seq1, seq2):
@lru_cache
def helper(idx1 = 0, idx2 = 0):
if idx1 == len(seq1) or idx2 == len(seq2):
return ''
if seq1[idx1] == seq2[idx2]:
return seq1[idx1] helper(idx1 1, idx2 1)
option1 = helper(idx1 1, idx2)
option2 = helper(idx1, idx2 1)
return max(option1, option2, key=len)
return helper()
seq1 = 'serendipitous'
seq2 = 'precipitation'
print(lcs_recursive(seq1, seq2)) # reipito
作為比較，使用seq1 = 'serendipitous'和seq2 = 'precipitation' lcs_recursive_uncached(seq1, seq2)進行 1119564 次遞回呼叫，而lcs_recursive_cached(seq1, seq2)僅進行 184 次遞回呼叫！：
number_of_calls_uncached = 0
def lcs_recursive_uncached(seq1, seq2, idx1 = 0, idx2 = 0, lcs = ''):
global number_of_calls_uncached
number_of_calls_uncached = 1
if idx1 == len(seq1) or idx2 == len(seq2):
return lcs
if seq1[idx1] == seq2[idx2]:
return lcs_recursive_uncached(seq1, seq2, idx1 1, idx2 1, lcs seq1[idx1])
else:
option1 = lcs_recursive_uncached(seq1, seq2, idx1 1, idx2, lcs)
option2 = lcs_recursive_uncached(seq1, seq2, idx1, idx2 1, lcs)
return max(option1, option2, key=len)
seq1 = 'serendipitous'
seq2 = 'precipitation'
print(number_of_calls_uncached) # 0
print(lcs_recursive_uncached(seq1, seq2)) # reipito
print(number_of_calls_uncached) # 1119564
from functools import lru_cache
number_of_calls_cached = 0
def lcs_recursive_cached(seq1, seq2):
@lru_cache
def helper(idx1 = 0, idx2 = 0):
global number_of_calls_cached
number_of_calls_cached = 1
if idx1 == len(seq1) or idx2 == len(seq2):
return ''
if seq1[idx1] == seq2[idx2]:
return seq1[idx1] helper(idx1 1, idx2 1)
option1 = helper(idx1 1, idx2)
option2 = helper(idx1, idx2 1)
return max(option1, option2, key=len)
return helper()
seq1 = 'serendipitous'
seq2 = 'precipitation'
print(number_of_calls_cached) # 0
print(lcs_recursive_cached(seq1, seq2)) # reipito
print(number_of_calls_cached) # 184
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/344896.html