最长的公共子序列，python，贪婪 [英] longest common subsequence, python, greedy
问题描述
我已经提交了有关两个序列的LCS问题的代码草案。我尝试贪婪时犯了严重错误，现在我已经实现了我相信针对此问题的稳定贪婪算法。尽管我有两个问题，但是这是在线课程的这一部分，当我提交它时，它说序列[1,2,3]和[3,2,1]的正确输出是1，我相信为什么？因此，我转到了正确的版本并进行了测试，它可以正常工作，即输出为0，并针对正确的版本对其进行了许多良好的测试案例的测试，它可以正常工作。现在，我有三个问题：
为什么[1,2,3]和[3,2,1]应该输出1而不是0？如果我的代码无效，请帮我做一些无效的测试用例？
谢谢！
我的代码：
def lcs2（a，b）：
lst，标记= []，如果len（set（a）.intersection（set（b）））！= 0则为假
！= 0：如果len（a）< = len（b）：x = a; y = b
else：x = b; y = y中i的
：如果i in x：
lst.append（x.index（i））
x [x.index（i）] =无
else：
y [i] =无
cnt = 0
对于i在range（1，len（lst））：
如果lst [i]> lst [i-1]：如果cnt == 0且未标记，则cnt + = 1
：返回0
返回cnt + 1
但是在测试<$ c时$ c> a = [-1，1，-1，-1，4]
b = [0，-1，0，4，4] 只是对我失败，给出正确答案2而不是1。
lcs2（[1、2、3]，[3、2、1]）正确返回 1 ，因为 [1] ， [2] 和 [3] 都是在两次运行中都出现的长度为1的序列的例子。
您的算法存在一些问题，似乎缺少某些情况。例如，它仅查找 y 中某个 y 元素的首次出现，但不会回溯寻找更长的序列。
此外，还不清楚为什么使用 tag ，因为它的唯一功能似乎是在检测两者是否相交set是空的（在这种情况下，结果仅为0，否则算法应查找1或更多的运行）。
一些运行不正常的示例使用您的算法： print（lcs2（[1、2、3]，[1、3、2、3]））（答案是2，但应该是3 ）-因为缺少回溯； print（lcs2（[]，[1]））失败，并出现IndexError，因为您尝试使用 y [i]访问空列表的元素] = None 。
由于 https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_for_the_dynamic_programming_solution 有很好的解决方案，无需复制$。 b
通常，不要试图通过尝试破坏随机示例来证明自己的代码，而应尝试考虑具有所有类型的变体并进行测试的示例集合该集。另外，请尝试完全了解您自己的算法，以便找出缺陷并可能对其进行优化。
I have already submitted a draft code for the LCS problem of two sequences. I made bad mistakes trying greedy, now I have implemented I believe a stable greedy algorithm for this problem. Though I have two issues, this part of an online course, when I submit it it says for sequences [1,2,3] and [3,2,1] the correct output is 1, where I believe Why? So, I went to the correct versions and tested, it works fine, that is the output is 0, and tested it for many good test cases against the correct versions, it works. Now, I have threequestions: Why [1,2,3] and [3,2,1] should output 1 instead of 0? If my code is not valid, please help me with some test cases that invalidate it? Thanks! My code:
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
Now, I take this one here, some proposed seemed to implement a good one:Python: Length of longest common subsequence of lists
But when testing it for a = [-1, 1, -1, -1, 4]
b = [0, -1, 0, 4, 4] it just fails against me, which gives the correct answer 2 rather than one.
lcs2([1, 2, 3], [3, 2, 1]) correctly returns 1, since [1], [2] and [3] are all examples of sequences of length 1 that are present in both runs.
Your algorithm has some issues and seems to missing some cases. For one, it only looks for the first occurrence of some element of y in x, but it doesn't backtrack to find longer sequences.
Also, it's unclear why you use tag as its only function seems to be detecting whether the intersection of the two sets is empty (in which case the result is just 0 and the algorithm should find runs of 1 or over otherwise).
Some examples of runs that don't work well with your algorithm: print(lcs2([1, 2, 3], [1, 3, 2, 3])) (answer is 2, but it should be 3) - this because of the lack of backtracking; print(lcs2([], [1])) this fails with an IndexError since you try to access elements of the empty list with y[i] = None.
I won't provide a working implementation, since https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_for_the_dynamic_programming_solution has good solutions that need not be replicated here.
In general, don't try to prove your code by thinking of random examples in an attempt to break it, but instead try to think of a collection of examples that have all types of variation and test against that set. Also, try to fully understand your own algorithm so you can reason out flaws and possibly optimise it.
这篇关于最长的公共子序列，python，贪婪的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
