python - 最长公共(public)子序列，python，贪婪

Question

我已经提交了两个序列的LCS问题的代码草案。我在尝试贪婪时犯了严重的错误，现在我已经实现了我相信这个问题的稳定贪婪算法。虽然我有两个问题，在线类(class)的这一部分，当我提交它时它说序列 [1,2,3] 和 [3,2,1] 正确的输出是 1，我相信为什么？所以，我去了正确的版本并进行了测试，它工作正常，即输出为 0，并针对正确的版本测试了许多好的测试用例，它工作正常。现在，我有三个问题:为什么 [1,2,3] 和 [3,2,1] 应该输出 1 而不是 0？如果我的代码无效，请帮我做一些使其无效的测试用例？谢谢!我的代码:

def lcs2(a, b):
    lst, tag= [], False
    if len(set(a).intersection(set(b))) != 0: tag = True 
    if len(a) <= len(b): x = a; y = b    
    else: x = b; y = a
    for i in y:
        if i in x:
            lst.append(x.index(i))
            x[x.index(i)] = None
        else:
            y[i] = None
    cnt = 0
    for i in range(1 ,len(lst)):
        if lst[i] > lst[i-1]: cnt += 1
    if cnt == 0 and not tag: return 0
    return cnt + 1

现在，我把这个带到这里，一些提议似乎实现了一个很好的:Python: Length of longest common subsequence of lists

但是当针对 a = [-1, 1, -1, -1, 4] 进行测试时
b = [0, -1, 0, 4, 4] 它只是对我失败了，它给出了正确答案 2 而不是一个。

Answer 1

lcs2([1, 2, 3], [3, 2, 1]) 正确返回 1，因为 [1] 、[2] 和 [3] 都是长度为 1 的序列的示例，它们出现在两次运行中。

您的算法存在一些问题，似乎遗漏了一些案例。首先，它只查找 x 中 y 的某个元素的第一次出现，但它不会回溯以查找更长的序列。

此外，不清楚为什么要使用 tag，因为它的唯一功能似乎是检测两个集合的交集是否为空(在这种情况下，结果仅为 0，算法应该找到运行1 或以上)。

一些不适合您的算法的运行示例:print(lcs2([1, 2, 3], [1, 3, 2, 3]))(答案是2，但应该是 3) - 这是因为缺少回溯； print(lcs2([], [1])) 由于您尝试使用 y[i] = None 访问空列表的元素，因此失败并出现 IndexError。

我不会提供有效的实现，因为 https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_for_the_dynamic_programming_solution有很好的解决方案，无需在此处复制。

一般来说，不要试图通过随机示例来证明您的代码以试图破坏它，而是尝试考虑具有所有类型变体的示例集合并针对该集合进行测试。此外，尝试完全理解您自己的算法，以便您可以找出缺陷并可能对其进行优化。