Получение самой длинной растущей подпоследовательности в Python

Может ли кто-нибудь сказать мне, почему этот код не создает каждую возрастающую подпоследовательность? Я использовал динамическое программирование, чтобы решить эту проблему, но я не могу понять, почему этот код терпит неудачу. Параметр A представляет собой последовательность целых чисел.Получение самой длинной растущей подпоследовательности в Python

def LIS(A): 

    # make a list of lists 
    L = list() 
    for i in range(0, len(A)): 
     L.append(list()) 

    #the first increasing subsequence is the first element in A 
    L[0].append(A[0]) 

    for i in range(1, len(A)): 
     for j in (0, i): 

      # a new larger increasing subsequence found 
      if (A[j] < A[i]) and (len(L[i]) < len(L[j])): 
       L[i] = L[j] 

     L[i].append(A[i]) 

     # print an increasing subsequence 
     print L[i]

Пример выходных данных производится при А = [3, 5, 10, 0, 1, 100, 2, 4, 7] по этому алгоритму:

[3, 5] 
[3, 5, 10] 
[0] 
[1] 
[3, 5, 10, 100] 
[2] 
[3, 5, 10, 100, 4] 
[3, 5, 10, 100, 4, 7] 
None

Правильный выход:

[3] 
[3, 5] 
[3, 5, 10] 
[0] 
[0, 1] 
[3, 5, 10, 100] 
[0, 1, 2] 
[0, 1, 2, 4] 
[0, 1, 2, 4, 7]

источник

2014-12-05 starhacker

Почему нет '' '[0, 1, 100]' '' valid? – wwii

Все, что вы пытаетесь сделать в своем внутреннем цикле, не работает, потому что вы всегда сравниваете первый элемент 'A' с' A [i] 'или' A [i] 'для себя -' '' (0, 1) '' 'не являются правильными вещами для итерации в' '' для j in (0, i): '' '. Я не вижу никаких доказательств того, что вы используете «динамическое программирование». – wwii

Поместите некоторые инструкции для печати, чтобы увидеть, что происходит - используйте ['' '' pprint.pprint (L) '' '] (https://docs.python.org/2.7/library/pprint.html#pprint.pprint) как последний оператор в функции, * после * внешний цикл * остановлен *. – wwii

Две ошибки, которые я нашел в своем коде

1.You вымышленного список неизменна, но они не в питоне

L[i] = L[j] this is going to make L[i] point to the same list pointed by L[j] 

2.for j in (0, i):

Это не итерация формы j от 0 до i-1, она итерации j формы от 0 до i.

Вот исправленная версия вашего кода.

def LIS(A): 

    # make a list of lists 
    L = list() 
    for i in range(0, len(A)): 
     L.append(list()) 

    # the first increasing subsequence is the first element in A 
    L[0].append(A[0]) 

    for i in range(1, len(A)): 
     for j in range(0, i): 

      # a new larger increasing subsequence found 
      if (A[j] < A[i]) and (len(L[i]) < len(L[j])): 
       'throw the previous list' 
       L[i] = [] 
       'add all elements of L[j] to L[i]' 
       L[i].extend(L[j]) 
     L[i].append(A[i]) 

    for i in range(len(A)): 
    # print an increasing subsequence 
     print (L[i]) 
A = [3, 5, 10, 0, 1, 100, 2, 4, 7] 
LIS(A)

источник

2014-12-31 14:14:51 akashchandrakar

Получение самой длинной растущей подпоследовательности в Python

ответ

Смежные вопросы