1

estoy tratando de escribir con python un programa que recupere la subsecuencia más larga de una lista de números dada mediante programación dinámica.

He conseguido realizar un algoritmo que calcula para cada elemento de la secuencia, la longitud de la mayor subsecuencia creciente que termina en cada posición, ejemplo:

ejemplo = [210, 816, 357, 107, 889, 635, 733, 930, 842, 542]



def subse(ejemplo):
    vector = [0 for i in range(len(ejemplo))]
    for i in range(len(ejemplo)):
        m = 0
        for j in range(i):
            if ejemplo[j] < ejemplo[i] and vector[j] > m:
                m = vector[j]
                
        vector[i] = m+1
        
        
    return vector

    
subse(ejemplo) 

Este programa devuelve:

[1, 2, 2, 1, 3, 3, 4, 5, 5, 3].

Ahora me gustaría escribir un programa que recupere la subsecuencia, es decir, que dado el máximo de la lista que he obtenido anteriormente (5) me devuelva los números por los que pasa para llegar a ese. Un resultado del algoritmo que quiero obtener sería, por ejemplo, para el caso del que hablo:

(5,[210, 357, 635, 733, 842])

Quería crear una lista en el algoritmo anteior donde ir guardando que índice genera cada uno de los número de la lista, así luego será fácil de recuperar (una especie de backpointer) pero no tengo muy claro como hacerlo. Si alguien puediese ayudarme se lo agradecería. Muchas gracias.

1 respuesta 1

1

Una aproximación sería combinar la lista que generas con la lista de entrada con zip para posteriormente convertirla en diccionario.

Con esto tendrías una asociación clave valor donde la clave es el índice de la subsecuencia y el valor el entero correspondiente basándonos en la lista de entrada.

Es decir:

ejemplo = [210, 816, 357, 107, 889, 635, 733, 930, 842, 542]
vector = [1, 2, 2, 1, 3, 3, 4, 5, 5, 3]

valores = zip(vector, ejemplo)
# Genera un objeto zip con esta estructura:
# [(1, 210), (2, 816), (2, 357), (0, 107), (3, 889), (3, 635), (4, 733), (5, 930), (5, 842), (0, 542)]

Convertir el objeto zip a dict directamente nos va a generar un problema si partimos de tu salida, ya que los valores se sobrescribirán tomando en cuenta la última aparición.

valores = dict(zip(vector, ejemplo))
# {1: 107, 2: 357, 3: 542, 4: 733, 5: 842}

Si nos fijamos en la posición 1 tenemos 107, que es la última aparición de la posición 1 teniendo en cuenta cómo se genera la variable vector

Para evitar esto podemos hacer una pequeña modificación en tu lógica. Sería simplemente asignar el valor a vector[i] sólo cuando sea mayor o igual que los valores anteriores.

        if m + 1 >= max(vector):
            vector[i] = m + 1

# El vector pasa a ser algo así
# [1, 2, 2, 0, 3, 3, 4, 5, 5, 0]

Esa modificación nos permite que al convertir el zip a diccionario tengamos este resultado:

{1: 210, 2: 357, 0: 542, 3: 635, 4: 733, 5: 842}

Con este diccionario ya preparado podemos eliminar la clave 0 y recuperar únicamente los valores:

del(valores[0])
out = valores.values()
# [210, 357, 542, 635, 733, 842]

Si tenemos en cuenta que en las keys tenemos el índice de la subsecuencia podemos recuperar la longitud máxima de esta con max(valores.keys())


Hay otras cosas que puedes modificar y/o tener en cuenta. Te doy varias ideas:

  • Para iterar por una lista no es necesario que utilices range(len(lista)). Si quieres acceder al índice de la lista puedes utilizar enumerate(lista):
for i, v in enumerate(ejemplo):

# i te devuelve la posición
# v te devuelve el elemento
  • Las subsecuencias no tienen por qué dar un resultado único. Quizá deberías buscar alguna forma de devolver todas las combinaciones o parametrizarlo para que devuelva la de menor valor (por ejemplo)

Resumiendo

Si utilizamos todo lo que te he expuesto quedaría así:

def subse(entrada):
    vector = [0 for _ in entrada]
    for i, v in enumerate(entrada):
        m = 0
        for j in range(i):
            if entrada[j] < v and vector[j] > m:
                m = vector[j]
        if m + 1 >= max(vector):
            vector[i] = m + 1

    valores = dict(zip(vector, entrada))
    del(valores[0])
    return max(valores.keys()), list(valores.values())

Con tus datos de ejemplo devolvería:

# (5, [210, 357, 635, 733, 842])
4
  • te puedes ahorrar la primera list comprehension si haces vector = [0]*entrada
    – Christian
    el 15 feb. 2022 a las 23:26
  • @Christian, no debería ser [0] * len(entrada)? No soy muy amigo de utilizar multiplicaciones a la hora de generar listas vacías por tema de referencias y siempre me genera dudas :/ el 16 feb. 2022 a las 10:12
  • Bueno no sé que tipo de dato sea entrada pero si es una lista entonces sip. El problema de referencia se genera cuando utilizas datos mutables por ejemplo listas ([[]]*3) pero no habrá problema con los números
    – Christian
    el 16 feb. 2022 a las 16:09
  • Es que NUNCA hay que usar multiplicaciones para crear listas de listas (o de objetos mutables en general), ya que como dices conlleva la creación de multiples referencias a la misma sublista. Para objetos inmutables (como numeros) no es tan grave,
    – Dante S.
    el 16 feb. 2022 a las 16:41

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.