0

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.

v_head
  • 759
  • 4
  • 13
  • One possibility is the Geeksforgeeks version seems to be designed for the parameters `X`, `Y` to be strings (of alpha characters), e.g. `"AGGTAB"`, and not a list of integers. So the operations would be different for `len()` of each of the parameters, and conditions comparing the values would be comparing the `ord()` value of the characters, whereas your code would be comparing the integer values. – chickity china chinese chicken Jan 10 '19 at 02:06
  • Exactly! I just removed i! – v_head Jan 10 '19 at 02:10
  • [1], [2], and [3] are all subsequences of both [1,2,3] and [3,2,1] – Matt Timmermans Jan 10 '19 at 02:23
  • Thanks, can you prove my algorithm incorrect – v_head Jan 10 '19 at 02:34

1 Answers1

0

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.

Grismar
  • 27,561
  • 4
  • 31
  • 54