В Python, как эффективно найти самый большой последовательный набор чисел в списке, которые не обязательно соседствуют?

Question

Например, если у меня есть список

[1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]

Этот алгоритм должен вернуть [1,2,3,4,5,6,7,8,9,10,11].

Чтобы уточнить, самый длинный список должен идти вперед.Мне было интересно, что является алгоритмически эффективным способом сделать это (предпочтительно не O (n ^ 2))?

Кроме того, я открыт для решения не в Python, так как алгоритм имеет значение.

Спасибо.

Answer 1

Вот простое однопроходное решение O (n):

s = [1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11,42]
maxrun = -1
rl = {}
for x in s:
    run = rl[x] = rl.get(x-1, 0) + 1
    print x-run+1, 'to', x
    if run > maxrun:
        maxend, maxrun = x, run
print range(maxend-maxrun+1, maxend+1)

Логика может быть немного более самоочевидной, если вы думаете в терминах диапазонов, а не отдельных переменных для конечной точки идлина пробега:

rl = {}
best_range = xrange(0)
for x in s:
    run = rl[x] = rl.get(x-1, 0) + 1
    r = xrange(x-run+1, x+1)
    if len(r) > len(best_range):
        best_range = r
print list(best_range)

Answer 2

Не такой умный, не O (n), может использовать немного оптимизации. Но это работает.

def longest(seq):
  result = []
  for v in seq:
    for l in result:
      if v == l[-1] + 1:
        l.append(v)
    else:
      result.append([v])
  return max(result, key=len)

Answer 3

Вы можете использовать Терпеливую сортировку реализацию алгоритма Самая большая восходящая подпоследовательность

def LargAscSub(seq):
    deck = []
    for x in seq:
        newDeck = [x]
        i = bisect.bisect_left(deck, newDeck)
        deck[i].insert(0, x) if i != len(deck) else deck.append(newDeck)
    return [p[0] for p in deck]

А вот и результаты теста

>>> LargAscSub([1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
>>> LargAscSub([1, 2, 3, 11, 12, 13, 14])
[1, 2, 3, 11, 12, 13, 14]
>>> LargAscSub([11,12,13,14])
[11, 12, 13, 14]

Порядок сложности O (nlogn)

Была одна заметка в вики-ссылке, где они утверждали, что вы можете достичь O (n.loglogn), полагаясь на Дерево Ван Эмде Боаса

Answer 4

Как насчет использования модифицированного Radix Sort ? Как указала JanneKarila, решение не является O (n). Он использует сортировку Radix, которая википедия говорит Radix sort's efficiency is O(k·n) for n keys which have k or fewer digits.

Это будет работать, только если вы знаете диапазон чисел, с которым мы имеем дело, так что это будет первый шаг.

1. Посмотрите на каждый элемент в стартовом списке, чтобы найти самое низкое, l и самое высокое, h число В этом случае l равно 1, а h равно 11. Обратите внимание: если вы по какой-то причине уже знаете диапазон, вы можете пропустить этот шаг.

2. Создайте список результатов размером нашего диапазона и установите для каждого элемента значение NULL.

3. Посмотрите на каждый элемент в списке и добавьте их в список результатов в соответствующем месте, если это необходимо. элемент равен 4, добавьте 4 в список результатов в позиции 4. result[element] = starting_list[element]. Вы можете выбросить дубликаты, если хотите, они просто будут перезаписаны.

4. Просмотрите список результатов, чтобы найти самую длинную последовательность без нулевых значений. Оставьте element_counter, чтобы знать, на какой элемент в списке результатов мы смотрим. Оставьте curr_start_element установленным для начального элемента текущей последовательности и оставьте curr_len длины текущей последовательности. Также сохраните longest_start_element и `longest_len ', которые будут начинаться с нуля и будут обновляться по мере продвижения по списку.

5. Возвращает список результатов, начиная с longest_start_element и принимая longest_len

РЕДАКТИРОВАТЬ: Код добавлен. Проверено и работает

#note this doesn't work with negative numbers
#it's certainly possible to write this to work with negatives
# but the code is a bit hairier
import sys
def findLongestSequence(lst):
    #step 1
    high = -sys.maxint - 1

    for num in lst:
        if num > high:
            high = num

    #step 2
    result = [None]*(high+1)

    #step 3
    for num in lst:
        result[num] = num

    #step 4
    curr_start_element = 0
    curr_len = 0
    longest_start_element = -1
    longest_len = -1

    for element_counter in range(len(result)):
        if result[element_counter] == None:

            if curr_len > longest_len:
                longest_start_element = curr_start_element
                longest_len = curr_len

            curr_len = 0
            curr_start_element = -1

        elif curr_start_element == -1:
            curr_start_element = element_counter

        curr_len += 1

    #just in case the last element makes the longest
    if curr_len > longest_len:
        longest_start_element = curr_start_element
        longest_len = curr_len


    #step 5
    return result[longest_start_element:longest_start_element + longest_len-1]

Answer 5

Хорошо, вот еще одна попытка в python:

def popper(l):
    listHolders = []
    pos = 0
    while l:
        appended = False
        item = l.pop()
        for holder in listHolders:
            if item == holder[-1][0]-1:
                appended = True
                holder.append((item, pos))
        if not appended:
            pos += 1
            listHolders.append([(item, pos)])
    longest = []
    for holder in listHolders:
        try:
            if (holder[0][0] < longest[-1][0]) and (holder[0][1] > longest[-1][1]):
                longest.extend(holder)
        except:
            pass
        if len(holder) > len(longest):
            longest = holder
    longest.reverse()
    return [x[0] for x in longest]

Примеры входов и выходов:

>>> demo = list(range(50))
>>> shuffle(demo)
>>> demo
[40, 19, 24, 5, 48, 36, 23, 43, 14, 35, 18, 21, 11, 7, 34, 16, 38, 25, 46, 27, 26, 29, 41, 8, 31, 1, 33, 2, 13, 6, 44, 22, 17,
 12, 39, 9, 49, 3, 42, 37, 30, 10, 47, 20, 4, 0, 28, 32, 45, 15]
>>> popper(demo)
[1, 2, 3, 4]
>>> demo = [1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]
>>> popper(demo)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
>>>

Answer 6

O (n) решение работает, даже если последовательность не начинается с первого элемента.

Предупреждение не работает, если len (A) = 0.

A = [1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]
def pre_process(A): 
    Last = {}
    Arrow = []
    Length = []
    ArgMax = 0
    Max = 0
    for i in xrange(len(A)): 
        Arrow.append(i)
        Length.append(0)  
        if A[i] - 1 in Last: 
            Aux = Last[A[i] - 1]
            Arrow[i] = Aux
            Length[i] = Length[Aux] + 1
        Last[A[i]] = i 
        if Length[i] > Max:
            ArgMax = i 
            Max = Length[i]
    return (Arrow,ArgMax)  

(Arr,Start) = pre_process(A) 
Old = Arr[Start] 
ToRev = []
while 1: 
    ToRev.append(A[Start]) 
    if Old == Start: 
        break
    Start = Old 
    New = Arr[Start]
    Old = New
ToRev.reverse()
print ToRev     

Python-ы приветствуются !!

Answer 7

Вам нужна Максимальная непрерывная сумма ( Оптимальная субструктура ):

def msum2(a):
    bounds, s, t, j = (0,0), -float('infinity'), 0, 0

    for i in range(len(a)):
        t = t + a[i]
        if t > s: bounds, s = (j, i+1), t
        if t < 0: t, j = 0, i+1
    return (s, bounds)

Это пример динамического программирования: O (N)

Answer 8

Предупреждение: это хитрый способ сделать это (иначе я использую python ...)

import operator as op
import itertools as it

def longestSequence(data):

    longest = []

    for k, g in it.groupby(enumerate(set(data)), lambda(i, y):i-y):
        thisGroup = map(op.itemgetter(1), g)

        if len(thisGroup) > len(longest):
            longest = thisGroup

    return longest


longestSequence([1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11, 15,15,16,17,25])

Answer 9

Если результат действительно должен быть подпоследовательностью последовательных возрастающих целых чисел, а не просто возрастающими целыми числами, то нет необходимости запоминать каждую целую последовательную подпоследовательность, пока вы не определите, какая издольше всего вам нужно помнить только начальные и конечные значения каждой подпоследовательности.Таким образом, вы могли бы сделать что-то вроде этого:

def longestConsecutiveSequence(sequence):
    # map starting values to largest ending value so far
    map = collections.OrderedDict()

    for i in sequence:
        found = False
        for k, v in map.iteritems():
            if i == v:
                map[k] += 1
                found = True

        if not found and i not in map:
            map[i] = i + 1

    return xrange(*max(map.iteritems(), key=lambda i: i[1] - i[0]))

Если я запускаю это в исходную дату выборки (т.е. [1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]), я получаю:

>>> print list(longestConsecutiveSequence([1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Если я запускаю его на одномиз выборок Абхиджита [1,2,3,11,12,13,14] я получаю:

>>> print list(longestConsecutiveSequence([1,2,3,11,12,13,14]))
[11, 12, 13, 14]

К сожалению, в худшем случае этот алгоритм равен O (n * n).

Answer 10

Это должно сработать (и это O (n)):

target = 1
result = []
for x in list:
    for y in result:
        if y[0] == target:
            y[0] += 1
            result.append(x)

Для любого начального номера это работает:

result = []
for x in mylist:
    matched = False
    for y in result:
        if y[0] == x:
            matched = True
            y[0] += 1
            y.append(x)
    if not matched:
        result.append([x+1, x])
return max(result, key=len)[1:]