Secuencia de serpientes más larga en una matriz

Pregunta: Un conjunto de números separados por espacio se pasa como entrada. El progtwig debe imprimir la secuencia de serpiente más grande presente en los números. Una secuencia de serpientes está formada por números adyacentes, de modo que para cada número, el número de la derecha o la izquierda es +1 o -1 de su valor. Si es posible realizar múltiples secuencias de serpientes de longitud máxima, imprima la secuencia de serpientes que aparece en el orden de entrada natural.

Ejemplo de entrada / salida 1:

Entrada:

9 8 7 5 3 0 1 -2 -3 1 2 

Salida:

 3 2 1 0 1 

Ejemplo de entrada / salida 2:

Entrada:

 -5 -4 -3 -1 0 1 4 6 5 4 3 4 3 2 1 0 2 -3 9 

Salida:

 6 5 4 3 4 3 2 1 0 -1 0 1 2 

Ejemplo de entrada / salida 3:

Entrada:

 5 6 7 9 8 8 

Salida:

 5 6 7 8 9 8 

He buscado en línea y solo he encontrado referencias para encontrar una secuencia de serpientes cuando se da una cuadrícula de números y no una matriz.

Mi solución hasta ahora:
Cree una matriz 2D que contenga todos los números de la entrada como 1 valor y el segundo valor sea la secuencia de longitud máxima que se puede generar a partir de ese número. Pero esto no siempre genera la secuencia de longitud máxima y no funciona en absoluto cuando hay 2 serpientes de longitud máxima.

Suponiendo que el orden en el conjunto original de números no importa, como parece ser el caso en su pregunta, esto parece ser una instancia del problema del camino más largo , que es NP-difícil.

Piénselo de esa manera: puede crear una gráfica a partir de sus números, con bordes entre todos los pares de nodos que tienen una diferencia de uno. Ahora, la ruta simple (acíclica) más larga en este gráfico es su solución. Tu primer ejemplo correspondería a este gráfico y ruta. (Tenga en cuenta que hay dos nodos 1 para los dos en el conjunto de entrada).

introduzca la descripción de la imagen aquí

Si bien esto en sí mismo no resuelve su problema, debería ayudarlo a comenzar a encontrar un algoritmo para resolverlo (o aproximarlo), ahora que conoce un nombre mejor / más común para el problema.


Un algoritmo funciona de la siguiente manera: a partir de cada uno de los números, determine los números “adyacentes” y realice una búsqueda en profundidad a través del gráfico para determinar la ruta más larga. Recuerde eliminar temporalmente los nodos visitados del gráfico. Esto tiene una complejidad peor de O (2 n ) 1) , pero aparentemente es suficiente para sus ejemplos.

 def longest_snake(numbers, counts, path): best = path for n in sorted(counts, key=numbers.index): if counts[n] > 0 and (path == [] or abs(path[-1] - n) == 1): counts[n] -= 1 res = longest_snake(numbers, counts, path + [n]) if len(res) > len(best): best = res counts[n] += 1 return best 

Ejemplo:

 >>> from collections import Counter >>> numbers = list(map(int, "9 8 7 5 3 0 1 -2 -3 1 2".split())) >>> longest_snake(numbers, Counter(numbers), []) [3, 2, 1, 0, 1] 

Tenga en cuenta que este algoritmo encontrará de manera confiable una secuencia máxima de “serpiente”, sin usar ningún número más seguido de lo permitido. Sin embargo, es posible que no encuentre la secuencia específica que se espera como salida, es decir, “la secuencia de serpiente aparece en el orden de entrada natural”, sea lo que sea que se supone que significa. Para acercarse al “orden natural”, puede probar los números en el mismo orden en que aparecen en la entrada (como lo hice con sorted ), pero eso tampoco funciona a la perfección. De todos modos, estoy seguro de que puedes resolver el rest por ti mismo.


1) En este caso especial, la gráfica tiene un factor de ramificación de 2, por lo tanto O (2 n ); en el caso más general, la complejidad sería más cercana a O (n!).