La subsecuencia única cada vez más larga.

Tengo una lista / matriz que se parece a esto:

[ 0 1 2 3 4 5 6 7 3 9 10 11 13 13 14 15 16 17 18 19 4 16 22 5 3 2 10 17 34 5 11 18 27 14 11 15 29 2 11 10 19 32 8 27 1 32 6 2 0] 

Esta lista se supone que es monotónica (estrictamente creciente). No lo es, pero puedes ver que está aumentando en su mayoría . Los valores que no encajan en este patrón pueden considerarse como ruido, y quiero que se eliminen. Así que quiero extraer el mayor subconjunto posible de esta lista, que será una secuencia estrictamente creciente de números. Hay muchas secuencias monotónicas posibles aquí, pero el punto es encontrar la más grande posible.

Es importante que obtenga los índices de los valores que se eliminarán, ya que necesito saber la posición exacta de los números restantes (por lo tanto, en lugar de eliminar números, podemos reemplazarlos con f.ex. None , nan o -1 ) .

No puedo cambiar el orden de ningún número, solo elimine los que no encajan.

La lista restante debe ser estrictamente creciente, por lo que si tenemos f.ex. [11 13 13 14] , ambos de los 13 tienen que ser eliminados.

Si hay varias soluciones posibles que son igualmente grandes, no podemos usar ninguna de ellas y debemos elegir una solución con 1 número menos. F.ex. en [27 29 30 34 32] tenemos que tirar 34 y 32, porque no podemos elegir uno sobre el otro. Si tenemos [27 29 34 15 32] no hay solución posible, porque no podemos elegir entre [27 29] , [27 34] , [29 34] o [15 32] .

La mejor solución posible para la lista presentada anteriormente sería esta:

 [ 0 1 2 3 4 5 6 7 -1 9 10 11 -1 -1 14 15 16 17 18 19 -1 -1 22 -1 -1 -1 -1 -1 -1 -1 -1 -1 27 -1 -1 -1 29 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1] 

¿Alguien puede pensar en un algoritmo que haría este trabajo específico? Si puedes traerme una parte en el camino, eso también sería apreciado.

Mi única idea hasta ahora es un bucle for n in range(N, 0, -1): donde N es el tamaño de la lista. El bucle primero intentaría encontrar soluciones de tamaño n=N , y luego para n=N-1 , n=N-2 , etc. Cuando encuentra exactamente 1 solución para una fuente específica, se detiene y devuelve esa solución. No estoy seguro de lo que debería estar dentro del bucle todavía.

ACTUALIZAR:

Otra pregunta SO proporciona un algoritmo de Python para encontrar la subsecuencia más larga de una lista. Esto es casi lo que quiero hacer, pero no del todo.

He copiado esa función (ver más abajo) y agregué un pequeño código adicional al final que cambió la salida if fullsize=True . Luego, se reconstruye la secuencia original con su forma original, pero los números que no forman parte de la secuencia creciente se reemplazan por nans. Y luego verifico si algún número aparece más de una vez, y si es así, reemplace todas las ocurrencias de ese número con nans.

El algoritmo original todavía debe cambiarse ya que no proporciona soluciones únicas.

Por ejemplo:

 a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 32, 18, 19, 20, 16, 35, 35, 33, 32, 1, 35, 13, 5, 32, 8, 35, 29, 19, 35, 19, 28, 32, 18, 31, 13, 3, 32, 33, 35, 31, 0, 21] print subsequence(a) 

da

 [ 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 32. nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan nan] 

En lugar de terminar con .. 16 32 nan .. debería haber terminado con ... 16 nan ... nan 31 nan nan 32 33 35 nan nan nan] , por lo que puedo ver.

Ejemplo más simple:

 a = [0,1,2,3,4,1,2,3,4,5] print subsequence(a) 

da

 [ 0. 1. 2. 3. nan nan nan nan nan 5.] 

pero solo debería haber dado [0 nan ... nan 5] porque 1 2 3 4 aparece dos veces y no es único.

Aquí viene la versión actual semi-funcional del código (que se usó para las ejecuciones de mi ejemplo):

 import numpy as np def subsequence(seq, fullsize=True): """ Credit: http://stackoverflow.com/questions/3992697/longest-increasing-subsequence """ M = [None] * len(seq) # offset by 1 (j -> j-1) P = [None] * len(seq) # Since we have at least one element in our list, we can start by # knowing that the there's at least an increasing subsequence of length one: # the first element. L = 1 M[0] = 0 # Looping over the sequence starting from the second element for i in range(1, len(seq)): # Binary search: we want the largest j <= L # such that seq[M[j]] < seq[i] (default j = 0), # hence we want the lower bound at the end of the search process. lower = 0 upper = L # Since the binary search will not look at the upper bound value, # we'll have to check that manually if seq[M[upper-1]]  1: mid = (upper + lower) // 2 if seq[M[mid-1]] < seq[i]: lower = mid else: upper = mid j = lower # this will also set the default value to 0 P[i] = M[j-1] if j == L or seq[i]  a: break if np.sum(subseq[np.where(subseq == a)].size) > 1: # Remove duplicates. subseq[np.where(subseq == a)] = np.nan return subseq # Alternative return made by me, PaulMag. 

Es un problema de progtwigción dinámica clásica.

Almacena para cada elemento la longitud de la secuencia más grande que termina en ese elemento. Para el primer elemento el valor es 1 (solo toma ese elemento). Para el rest, toma el máximo (1, 1 + el valor asignado a algún otro elemento anterior que es <= entonces el elemento actual).

Se puede implementar con 2 bucles (O (N ^ 2)). Probablemente hay algunas optimizaciones que puedes hacer si tus datos son realmente grandes. O saber que su secuencia es buena en general, solo compruebe los elementos X anteriores.

Para arreglar sus datos, comienza con uno de los valores máximos asignados (que es la longitud de la secuencia monótona más larga), reemplaza con -1 todo después, luego retroceda por la lista buscando el elemento anterior en la secuencia (debería ser < = entonces el actual y el valor asignado deben ser -1 a lo que se asigna el elemento actual), mientras que no encuentra una coincidencia, ese elemento no pertenece. Cuando encuentras una coincidencia, la tomas como la actual y continúas hacia atrás hasta que encuentres un elemento al que has asignado 1 (ese es el primero).