最长的子序列,算法工作错误,不明白为什么

Question

我实现了最长增加子序列(LIS)算法,因为我认为它会起作用,但结果完全是混乱的.

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

返回结果:

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

应该是什么:

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

正如我在调试器中看到的那样:

L[i] = L[j]

不仅L[i]获得新值,而且列表中的其他main (L)列表也是......

我不知道如何避免它.看起来Python中的列表与C系列中的矢量语言完全不同......

我和它打了很长时间.巨大的啤酒给那些会发现错误的人:(

Answer 1

当您声明L[i] = L[j] 不复制列表的内容时,您只需复制一个引用:从现在开始L[i]并L[j]指向相同的列表,所做的更改L[i]将反映您获取的时间L[j].

简单的修复只是复制列表:

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)

现在,你的算法不再适用(尽管如此,它还没有工作).运行(固定)代码时,您会得到:

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

将3在第一个列表中出现了两次,你可以通过删除解决这个问题.append的前for环.所以最终的版本是:

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)

哪个产生:

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

注意:基于你的评论你使用python-2.7,从python-3.x有一个叫做.copy()列表的方法你可以调用.