En python, ¿cómo se puede encontrar de manera eficiente el mayor conjunto de números consecutivos en una lista que no son necesariamente adyacentes?

Question

Por ejemplo, si tengo una lista

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

Este algoritmo debe devolver [1,2,3,4,5,6,7,8,9,10,11].

Para aclarar, la lista más larga debe ejecutarse hacia adelante. Me preguntaba ¿cuál es una manera algorítmicamente eficiente de hacer esto (preferiblemente no O (n^2))?

Además, estoy abierto a una solución que no está en Python ya que el algoritmo es lo que importa.

Gracias.

Answer 1

Aquí es un simple de una sola pasada O solución (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) 

La lógica puede ser un poco más evidente si se piensa en términos de intervalos en lugar de las variables individuales para el punto final y de ejecución longitud:

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

Esto debería hacer el truco (y es O (n)):

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

Para cualquier número de partida, esto funciona:

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:] 

Answer 3

se puede utilizar el Patience Sort aplicación de la Largest Ascending Sub-sequence Algorithm

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] 

Y aquí está la Resultados de prueba

>>> 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] 

El orden de complejidad es O (nlogn)

Había una nota en el enlace wiki en el que afirmaban que se puede lograr O (n.loglogn) apoyándose en Van Emde Boas tree

Answer 4

No tan inteligente, no O (n), podría usar un poco de optimización. Pero funciona.

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 5

Cómo sobre el uso de un modificado Radix Sort? Como JanneKarila señaló que la solución no es O (n). Utiliza el género Radix, que wikipedia dice Radix sort's efficiency is O(k·n) for n keys which have k or fewer digits.

Esto solo funcionará si conoce el rango de números con el que estamos tratando, de modo que será el primer paso.

1. vistazo a cada elemento de la lista que comienza a encontrar más bajo, y la más alta l, h número. En este caso, l es 1 y h es 11. Nota: si ya conoce el rango por algún motivo, puede omitir este paso.

2. Cree una lista de resultados del tamaño de nuestro rango y configure cada elemento como nulo.

3. Mire cada elemento en la lista y agréguelos a la lista de resultados en el lugar apropiado si es necesario. es decir, el elemento es un 4, agregue un 4 a la lista de resultados en la posición 4. result[element] = starting_list[element]. Puede tirar duplicados si lo desea, solo se sobrescribirán.

4. Consulte la lista de resultados para encontrar la secuencia más larga sin ningún valor nulo. Mantenga un element_counter para saber qué elemento de la lista de resultados estamos viendo.Mantenga un curr_start_element establecido en el elemento inicial de la secuencia actual y mantenga un curr_len de la longitud de la secuencia actual. También mantenga un longest_start_element y un `longest_len 'que comenzará como cero y se actualizará a medida que avancemos por la lista.

5. devolver el listado de resultados a partir de las longest_start_element y tomando longest_len

EDIT: Código añadió. Probado y trabajando

#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 6

Si el resultado realmente no tiene que ser una sub-secuencia de enteros ascendentes consecutivos, en lugar de números enteros simplemente ascendente, entonces no hay necesidad de recordar cada uno toda sub-secuencia consecutiva hasta que se determine cuál es el más largo, solo necesita recordar los valores iniciales y finales de cada subsecuencia. Por lo que podría hacer algo como esto:

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])) 

Si funciono esto en la fecha original de la muestra (es decir [1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]) me sale:

>>> 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] 

Si lo ejecuto en una de las muestras de Abhijit [1,2,3,11,12,13,14], me consiga:

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

Lamentablemente, este algoritmo es O (n * n) en el peor de los casos.

Answer 7

Advertencia: Esta es la forma de hacerlo cheaty (también conocido como utilizo pitón ...)

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 8

Es necesario el máxima suma contigua (Optimal Substructure):

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) 

Este es un ejemplo de programación dinámica y es O (N)

Answer 9

funciona O solución (n) incluso si la secuencia no se inicia del primer elemento.

advertencia no funciona si Pythonizations 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  

son bienvenidos !!

Answer 10

autorización, aquí es otro intento en 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] 

entradas y salidas de la muestra:

>>> 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] 
>>>