Search code examples
pythonalgorithmlistlis

Longest increasing subsequence, algorithm works wrong, no idea why

I made an implementation of Longest Increasing Subsequence (LIS) algorithm, as I see it would work, but results are totally mess.

def lis():
    #D = map(int, raw_input().split())
    D = [3, 2, 6, 4, 5, 1]
    L = [[] for i in range(len(D))]
    L[0].append(D[0])
    for i in range(len(D)):
        for j in range(0,i):
            if D[i] > D[j]:
                L[i] = L[j]
        L[i].append(D[i])
    print L

Returned result:

[[3], [2, 6, 4, 5], [2, 6, 4, 5], [2, 6, 4, 5], [2, 6, 4, 5], [1]]

What it should be:

[[3], [2], [2, 6], [2, 4], [2, 4, 5], [1]]

As I saw in debugger when we have:

L[i] = L[j]

Not only L[i] gets new values, but other lists on the main (L) list too...

I don't know how to avoid it. It looks that lists in Python are totally different than vectors languages from C family...

I'm fighting with this for a long time. Huge beer to someone who gonna find what is wrong :(

Solution

  • When you state L[i] = L[j] you do not copy the content of the list, you simply copy a reference: from now on L[i] and L[j] point to the same list and changes made through L[i] will reflect when you obtain L[j].

    A simply fix is simply to copy the list:

    def lis():
    #D = map(int, raw_input().split())
    D = [3, 2, 6, 4, 5, 1]
    L = [[] for i in range(len(D))]
    L[0].append(D[0])
    for i in range(len(D)):
        for j in range(0,i):
            if D[i] > D[j]:
                L[i] = list(L[j])
        L[i].append(D[i])
    print(L)

    Now hoever your algorithm does not work anymore (it was not working in the first place nevertheless). When running your (fixed) code, you get:

    >>> lis()
[[3, 3], [2], [2, 6], [2, 4], [2, 4, 5], [1]]

    The 3 occurs twice in the first list, you can solve this by removing the .append before the for loop. So the final version is:

    def lis():
    #D = map(int, raw_input().split())
    D = [3, 2, 6, 4, 5, 1]
    L = [[] for i in range(len(D))] #removed the next line
    for i in range(len(D)):
        for j in range(0,i):
            if D[i] > D[j]:
                L[i] = list(L[j])
        L[i].append(D[i])
    print(L)

    Which produces:

    >>> lis()
[[3], [2], [2, 6], [2, 4], [2, 4, 5], [1]]

    Note: based on your comment you use , from there is a method called .copy() on lists that you can call.