Longest Common Subsequence, Python, Greedy

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 p

Solution 1:

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.