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

Ответ 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)

Ответ 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)

Ответ 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)

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

Ответ 4

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

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

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

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

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

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

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

EDIT: добавлен код. Протестировано и работает

#note this doesn't work with negative numbers
#it 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]

Ответ 5

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

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]

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

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

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

Ответ 6

Предупреждение: Это обманный способ сделать это (иначе я использую 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])

Ответ 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)

Ответ 8

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     

Питонизации приветствуются!

Ответ 9

Хорошо, вот еще одна попытка в 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]
>>>

Ответ 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:]