In python, in che modo si trova efficientemente il numero maggiore di numeri consecutivi in ​​un elenco che non è necessariamente adiacente?

Question

Per esempio, se ho una lista

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

Questo algoritmo deve restituire [1,2,3,4,5,6,7,8,9,10,11].

Per chiarire, l'elenco più lungo deve essere eseguito in avanti. Mi stavo chiedendo quale sia un modo algoritmicamente efficiente per farlo (preferibilmente non O (n^2))?

Inoltre, sono aperto a una soluzione non in python poiché l'algoritmo è ciò che conta.

Grazie.

Answer 1

Ecco un semplice O-pass uno (n) Soluzione:

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 logica può essere un po 'più evidente se si pensa in termini di range invece di singole variabili per il punto finale e corsa lunghezza:

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

Questo dovrebbe fare il trucco (ed è O (n)):

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

Per qualsiasi numero di partenza, questo funziona:

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

è possibile utilizzare il Patience Sort attuazione del 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] 

Ed ecco i risultati del test

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

L'ordine di complessità è O (nlogn)

C'era una nota nel link wiki dove hanno sostenuto che è possibile ottenere O (n.loglogn) affidandosi a Van Emde Boas tree

Answer 4

Non che intelligente, non O (n), potrebbe utilizzare un po 'di ottimizzazione. Ma funziona.

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

Come utilizzare un Radix Sort modificato? Come JanneKarila ha sottolineato, la soluzione non è O (n). Usa ordinamento Radix, che dice wikipedia Radix sort's efficiency is O(k·n) for n keys which have k or fewer digits.

Questo funzionerà solo se conoscete l'intervallo di numeri con cui abbiamo a che fare in modo che sia il primo passo.

1. guardare ad ogni elemento della lista di partenza per trovare più basso, l e più alto, h numero. In questo caso l è 1 e h è 11. Nota, se si conosce già l'intervallo per qualche motivo, è possibile saltare questo passaggio.

2. Creare un elenco di risultati delle dimensioni del nostro intervallo e impostare ogni elemento su null.

3. Controllare ciascun elemento nell'elenco e aggiungerli all'elenco dei risultati nel punto appropriato, se necessario. cioè, l'elemento è un 4, aggiungi un 4 alla lista dei risultati nella posizione 4. result[element] = starting_list[element]. Puoi buttare via i duplicati se vuoi, saranno semplicemente sovrascritti.

4. Passare attraverso l'elenco dei risultati per trovare la sequenza più lunga senza valori nulli. Tieni un element_counter per sapere quale elemento nell'elenco dei risultati stiamo guardando.Mantenere un curr_start_element impostato sull'elemento iniziale della sequenza corrente e mantenere un valore curr_len della durata della sequenza corrente. Conserva anche uno longest_start_element e un `longest_len 'che inizieranno come zero e saranno aggiornati man mano che ci sposteremo nella lista.

5. Ritorna alla lista dei risultati a partire da longest_start_element e tenendo longest_len

EDIT: Codice aggiunto. Testato e funzionante

#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

Se il risultato realmente deve essere una sotto-sequenza di consecutivi interi ascendenti, piuttosto che interi semplicemente ascendente, allora non c'è bisogno di ricordare ogni intero sub-sequenza consecutiva fino a determinare quale sia la più lunga, è sufficiente ricordare solo i valori iniziali e finali di ciascuna sottodirectory. Così si potrebbe fare qualcosa di simile:

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

Se eseguo questo alla data di campione originale (cioè [1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]) ottengo:

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

Se l'eseguo su uno dei campioni [1,2,3,11,12,13,14] di Abhijit, ho get:

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

Purtroppo questo algoritmo è O (n * n) nel peggiore dei casi.

Answer 7

Attenzione: Questo è il modo per farlo cheaty (aka io uso 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 8

È necessario il massima somma 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) 

Questo è un esempio di programmazione dinamica ed è O (N)

Answer 9

O (n) soluzione funziona anche se la sequenza non si avvia dal primo elemento.

Attenzione non funziona se 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  

Pythonizations sono i benvenuti !!

Answer 10

Ok, ecco l'ennesimo tentativo in 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] 

ingressi e le uscite di esempio:

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