Longest Zig Zag Subsequence: Análisis de la solución

Ayer el M.Sc. Jorge Terán, en la materia INF-143 nos planteó este problema… la solución se realizaba mediante dos vectores de tamaño n (donde n es la cantidad de datos). Sin embargo, también se puede solucionar mediante un solo vector de tamaño n, con una complejidad algorítmica de O(n)…

Ahora que tengo tu atención, voy a explicar cómo llegar a esta solución, y luego explicaré cómo es que esta solución funciona XD

Pero primero, sobre lo que encontrarás, y lo que no encontrarás aquí: Si estás esperando encontrar deliciosa copy-pasta del código para terminar tu tarea, te haz equivocado de post! por el contrario, si lo que buscas es entender la solución del problema, este post es para tí!

Statement: (Resúmen)

Para una descripción completa del problema, puedes ver el enunciado que M.Sc. Terán nos pasó en clases

Dada una secuencia de números en determinado orden, esta secuencia se denomina “secuencia zig-zag” si el número que resulta de restar el primer número del segundo, es de un signo distinto que el número que resulta de restar el segundo número del tercero… y este a su vez, es de signo distinto que el resultado de la resta del tercero con el cuarto… y así sucesivamente.

Se asume que el 0 es positivo y negativo ( demostración matemática), por lo que tiene el mismo signo que un número positivo y que un número negativo, y por lo tanto, cualquier secuencia que tenga dos números iguales seguidos, no es una secuencia zigzag.

Por ejemplo:


Datos:   1    5    3   30    8    16  15
Restas:   -4    2   -27   22  -8    1
Signos:   (-)  (+)  (-)  (+)  (-)  (+)

Esta es una secuencia zigzag, porque los signos de sus restas están intercalados.

Dada una secuencia de números, determinar la longitud de la subsequencia zig-zag más grande que se pueda formar con éstos números

una subsecuencia se puede formar eliminando cualquier número de cualquier posición de la secuencia original.

Buscando una solución

cómo sabemos si una secuencia de números es una secuencia zig-zag?

Para determinar esto, necesitamos la resta de los números de la secuencia…


Datos:   1    5    3   30    8    16  15
Restas:   -4    2   -27   22  -8    1

Más concretamente, necesitamos saber la polaridad


Signos:   (-)  (+)  (-)  (+)  (-)  (+)

Eso es! negativo, positivo, negativo, positivo, … eso es lo que buscamos en los números: que:
si hay una resta negativa: después tiene que haber, o bien nada, o bien una resta positiva.

Si hay una resta positiva: después tiene que haber, o bien nada, o bien una resta negativa.

De vuelta al problema… hay que encontrar la subsecuencia zig-zag más larga dentro de una secuencua dada de números. Puedo hacer esto si lo veo como un juego:

¿Cómo convierto una secuencia de números cualquiera, en una secuencia de números zig-zag eliminando la menor cantidad de números posible? Si de convertir se trata, entonces necesitaremos algo más que la polaridad de las restas: también necesitaremos la cantidad de las restas, para saber cuándo un (+) se puede convertir en un (-) luego de eliminar algún número de la secuencia.

Intentemos resolver un problema usando nuestro razonamiento… veamos este caso:


indice: 0   1   2   3   4   5   6   7    8   9
Datos:  1   17  5   10  13  15  10  5    16  8 
Restas:  -16  12  -5  -3  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (-) (+) (+) (-)  (+)

Comenzando de izquierda a derecha, podemos ver: -, +, -, ¡-! y encontramos la primera incongruencia en el índice 4! ¿Qué hacemos? tenemos dos opciones:
1 STEP-FORWARD: borrar el índice 4
2 STEP-BACKWARD: borrar el índice 3

¿Cuál de estas dos nos conviene más? no lo sabemos: hay que probar ambas, y ver con cuál se realizarían menos eliminaciones… probemos step-forward: eliminaremos el índice 4:

intentando step-forward


indice: 0   1   2   3   4   5   6   7    8   9
Datos:  1   17  5   10  13  15  10  5    16  8 
Restas:  -16  12  -5  -3  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (-) (+) (+) (-)  (+)

*luego de eliminar el índice 4*


indice: 0   1   2   3   4   5   6    7   8 
Datos:  1   17  5   10  15  10  5    16  8 
Restas:  -16  12  -5  -5   5   5   -11   8
Signos:  (-)  (+) (-) (-) (+) (+) (-)  (+)

AAAJÁ!!!!! vieron lo que pasó? lo vieron?! cada vez que eliminas al iésimo número del vector de datos, el iésimo-1 número del vector de restas se suma con el número que tiene a su derecha :D

Ahora, parece obvio que no necesitaremos el vector de datos (de hecho, tampoco necesitaremos un vector de índices ni de signos, pero los dejaremos visibles, ya que ayudan a entender el problema). todo lo que necesitamos es un vector en el que almacenamos las restas de los números!

volvamos a intentar solucionarlo… luego de eliminar el índice 4, se resolvió el problema? parece que no: el problema no se va a solucionar, hasta que el signo del 3er elemento del vector de restas cambie a positivo… así que volvamos a eliminar al índice 4, y hagámoslo hasta que el 3er elemento en el vector de restas se vuelva positivo no olviden que solo hemos eliminado 1 item


indice: 0   1   2   3   4    5    6    7 
Datos:  1   17  5   10  10   5    16   8 
Restas:  -16  12  -5  0    5   -11   8
Signos:  (-)  (+) (-) (?) (+)  (-)   (+)

nope… hay que volver a eliminar el 4… ya llevamos 2 eliminados


indice: 0   1   2   3   4    5    6  
Datos:  1   17  5   10  5    16   8 
Restas:  -16  12  -5  5   -11   8
Signos:  (-)  (+) (-) (+) (-)  (+)

esto sí soluciona el problema! y hemos eliminado a 3 números

¿Qué habría pasado si hubieramos intentado step-backward?

intentando step-backward…

En este camino, intentamos eliminar al número índice 3…


indice: 0   1   2   3   4   5   6   7    8   9
Datos:  1   17  5   10  13  15  10  5    16  8 
Restas:  -16  12  -5  -3  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (-) (+) (+) (-)  (+)

luego de eliminar el índice 3…


indice: 0   1   2   4   4   5   6   7    8  
Datos:  1   17  5   13  15  10  5    16  8 
Restas:  -16  12  -8  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (+) (+) (-)  (+)

esto no solucionó el problema… ¿Cuándo se solucionará el problema? cuando el número que está a la derecha del índice 3 del vector de las restas cambie de signo! así que vamos a repetir éste proceso, hasta que el 4to índice del vector de restas se vuelva positivo…

 

¿Qué problemas podrían surgir aquí? podría suceder que… de pronto, en una de las eliminaciones, el número del vector de restas que estamos analizando (el que está en negrillas en el código de arriba), cambie de signo, porque entonces, ya no sería congruente con el número anterior, y tendríamos que volver a analizar tooodo el vector. Pero esto no va a pasar porque, para que esto pase, es necesario que el número que está a la derecha de él tenga un signo diferente al número que estamos analizando, y cuando esto suceda, el problema se habrá solucionado, por lo que no sería necesario eliminarlo!

hasta ahora hemos eliminado 1 número

eliminamos el 4to…


indice: 0   1   2   4   4   5   6   7  
Datos:  1   17  5   15  10  5    16  8 
Restas:  -16  12  -10  5   5   -11   8
Signos:  (-)  (+) (-)  (+) (+) (-)  (+)

Esto soluciona el problema! hemos eliminado 2 números

Así que comparemos: qué solución es mejor en este caso?
STEP-BACKWARD: elimina 2 números.
STEP-FORWARD: elimina 3 números.

Creo que es mejor quedarnos con STEP-BACKWARD, ya que solo elimina 2 números.

Más adelante, nos queda un problema por resolver: dos signos + repetidos! creo que la lógica se ha entendido, así que, no lo resolveré paso por paso.

La Secuencia Zig-Zag más larga que se puede formar, es esta:


indice: 0   1   2    4   4   5    6  
Datos:  1   17  5    15  10  16   8 
Restas:  -16  12  -10  5   -6   8
Signos:  (-)  (+) (-)  (+) (-) (+)

y se forma luego de realizar 3 eliminaciones… su longitud es 7=10-3;

La Solución

“Pero dijiste que era una solución que funcionaba en O(n)!! yo solo veo una gran y obvia recurrencia…”

Con este razonamiento, se puede lograr una solución que funciona en O(n)… en serio! no es tan complicado como parece…

Ya que nos convencimos de que no necesitaremos el vector de los datos, transformaremos esto:


indice: 0   1   2   3   4   5   6   7    8   9
Datos:  1   17  5   10  13  15  10  5    16  8 
Restas:  -16  12  -5  -3  -2  5   5   -11   8
Signos:  (-)  (+) (-) (-) (-) (+) (+) (-)  (+)

en esto


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8

Como solo vamos a recorrer el vector una vez, imagina que este eres tú: ·u· y que estás en el primer elemento del vector:


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:      ·u·

Así que vas a recorrer el vector hasta que encuentres la primera incoherencia, así:


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:      ·u·


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:           ·u·


indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:               ·u·

¡haz encontrado tu primera incoherencia! tienes dos opciones: step-forward o step-backward… así que te declaras dos variables: fw=0 (para step-forward) y bw=0 (para step-backward), también te creas otra variable llamada j… y las inicializas así:


bw+=restas[j-1]; fw+=restas[j]
indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:               ·u·
J:                     j

mientras vas incrementando j… ¿Hasta cuándo hay que repetirlo? hasta que j se salga del vector, o mientras bw tenga el mismo símbolo que restas[j+1] o mientras fw tenga el mismo símbolo que restas[·u·]

¿Por qué? porque bw indica cómo quedaría el número con índice 2 si decides tomar la solución step-backward, así que, en cuanto el número de la derecha (luego de sumarle ‘j’ números) cambie de signo, entonces el problema se habrá solucionado, y se asumirá que se han hecho ‘j – ·u·’ eliminaciones.

Mientras que fw indica cómo quedaría el número con índice 3 si decides tomar la solución step-forward… es casi la misma lógica…

si j se sale del rango, es porque hay que eliminar a todos los que están a partir de tu posición.


bw+=-5; fw+=-3;
indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:               ·u·
J:                     j


bw+=-8; fw+=-5;
indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:               ·u·
J:                        j

¡aquí se cumple una condición de salida!
bw es de diferente signo que restas[j+1], por lo tanto, la mejor solución, es backward, en la que se realizan 2 eliminaciones.

Añades las 2 eliminaciones al contador de eliminaciones, saltas hasta j, y continúas tu camino hasta volver a encontrar una incoherencia… si vuelves a encontrar una incoherencia, repites el proceso…


contador de eliminaciones: 2;
indice:  0    1   2   3   4   5   6   7     8
Restas:  -16  12  -5  -3  -2  5   5   -11   8
TÚ:                       ·u·

¡Eso es todo! ahora… a codificar! :D

Si se fijan con atención, con este algoritmo, únicamente es necesario recorrer una vez el vector de restas (que tiene una longitud de n-1), lo cual nos da una complejidad algoritmica de O(n-1) = O(n). Además, si al momento de la lectura de los datos, en vez de almacenarlos en un vector, se restan y estas restas se almacenan directamente en un vector, este algoritmo ocuparía un espacio de O(n).

Advertisements