Как написать функцию для поиска самой длинной общей подпоследовательности с помощью динамического программирования c? - PullRequest
Новая
       25

Как написать функцию для поиска самой длинной общей подпоследовательности с помощью динамического программирования c?

0 голосов
/ 02 апреля 2020

Для ясности, я ищу саму последовательность, а не длину. Я написал эту функцию, которая работает большую часть времени, но в некоторых случаях она не работает. Я должен написать это рекурсивно без каких-либо циклов или импорта. Я использовал функцию memoise для большей эффективности, но не включил ее здесь.

Эта функция работает, когда s1 = "abcde" и s2 = "qbxxd" (которая правильно возвращает "bd"), но это не ' не работает, когда s1 = "Посмотри на меня, я могу летать!" и s2 = "Посмотри на это, это муха", которая должна возвращать "Посмотри на муху", но вместо этого я получаю "Посмотри на муху". По какой-то причине запятая и пробел игнорируются. Я пробовал s1 = "ab, cde" и s2 = "qbxx, d", который правильно возвращает "b, d". 

def lcs(s1, s2):
"""y5tgr"""
i = len(s1)
j = len(s2)
if i == 0 or j == 0:
    return ""
if s1[i-1] == s2[j-1]:
    return lcs(s1[:-1], s2[:-1]) + s1[i-1]
else:
    return max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]))

У меня такое ощущение, что проблема в последней строке и Макс функция. Я видел решения с циклами for и while, но не без них.

Ответы [ 2 ]

1 голос
/ 02 апреля 2020

Существует только небольшое изменение, чтобы исправить ваш код (вы правы, проблема была в максимуме).

Просто измените max, чтобы он нашел строку максимальной длины , используя свой ключ функция. 

def lcs(s1, s2):
    """y5tgr"""
    i = len(s1)
    j = len(s2)
    if i == 0 or j == 0:
        return ""
    if s1[i-1] == s2[j-1]:
        return lcs(s1[:-1], s2[:-1]) + s1[i-1]
    else:
        # Find max based upon the string length
        return max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]), key=len)

Однако, это очень медленно без запоминания

Код с памяткой (для улучшения производительности)

Декоратор памятки Ссылка 

import functools

def memoize(obj):
    cache = obj.cache = {}

    @functools.wraps(obj)
    def memoizer(*args, **kwargs):
        if args not in cache:
            cache[args] = obj(*args, **kwargs)
        return cache[args]
    return memoizer

@memoize
def lcs(s1, s2):
    """y5tgr"""
    i = len(s1)
    j = len(s2)
    if i == 0 or j == 0:
        return ""
    if s1[i-1] == s2[j-1]:
        return lcs(s1[:-1], s2[:-1]) + s1[i-1]
    else:
        return max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]), key=len)

Тест 

s1 = "Look at me, I can fly!"
s2 = "Look at that, it's a fly"
print(lcs(s1, s2))

Выход 

Look at ,  a fly
0 голосов
/ 02 апреля 2020

Для строк max принимает строку, которая лексикографически идет последней: 

>>> max("a", "b")
'b'
>>> max("aaaaa", "b")
'b'
>>>

Конечно, не то, что вам нужно; Вы, кажется, ищете длиннее из двух. Вам не нужен al oop, просто сравнение: 

lsc1 = lcs(s1[:-1], s2)
lcs2 = lcs(s1, s2[:-1])
return lcs1 if len(lcs1) > len(lcs2) else lcs2
...