Самая длинная возрастающая подпоследовательность, алгоритм работает неправильно, не знаю почему

Я реализовал алгоритм Longest Increasing Subsequence (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...

Я с этим борюсь давно. Огромное пиво тому, кто найдет, что не так :(


python list algorithm lis
person Adamm    schedule 18.01.2017    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Когда вы указываете 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() для списков, который вы можете вызвать.

person Willem Van Onsem    schedule 18.01.2017
comment
@Adamm: имейте в виду, что ваш алгоритм сломается (ну, он уже был сломан). Кажется, я добавил исправление. - person Willem Van Onsem; 18.01.2017
comment
У меня возникла небольшая проблема с: L[i] = L[j].copy(), AttributeError: объект 'list' не имеет атрибута 'copy', но вместо него помещается L[i] = list(L[j]) , это правильно? - person Adamm; 18.01.2017
comment
@Adamm: да, вы используете python-2.7? В python-3.x доступен copy. - person Willem Van Onsem; 18.01.2017
comment
Да, 2.7, так что пришлось внести мелочь, всем спасибо, ура! - person Adamm; 18.01.2017

arrow_upward
0
arrow_downward

Важное примечание

Приведенное выше решение является правильным, но если вы попробуете его, в некоторых случаях результат может быть неправильным. Например, самая длинная возрастающая подпоследовательность чисел:

5 1 4 2 3 1 2 9 1

is

1 2 3 9

Но этого решения не будет в вашем списке L, возвращаемом алгоритмом. Будет:

1 2 9

Требуется максимальный элемент из списка L. Затем можно добавить еще один элемент из D, поэтому нам нужно добавить еще одно условие, вот вам правильный код:

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

>>lis()
[[5], [1], [1, 4], [1, 2], [1, 2, 3], [1], [1, 2], [1, 2, 3, 9], [1]]
person Adamm    schedule 18.01.2017