Python Quiz 7 – Aplanar listas anidadas en Python

pyquiz 7 - aplanar listas anidadas en Python

Pregunta principal del PyQuiz:

def flatter(lst):
    ret = []
    for elem in lst:
        if isinstance(elem, list):
            ret.extend(flatter(elem))
        else:
            ret.append(elem)
    return ret
>>> print(flatter([1, ['pepe'], ['Juan', [['Ana']]]]))
- ?? -
# A - [1, 'pepe', 'Juan', 'Ana']
# B - RuntimeError
# C - [1, 'pepe', ['Juan', ['Ana']]]

Concepto y explicación

En esta pregunta hay muchos conceptos a destacar, por lo que se van a estudiar detenidamente cada parte. Vamos a ello ;).

La idea principal de este ejercicio es poder analizar código recursivo que sirve para aplanar listas anidadas. Por lo tanto, partiendo de una lista que puede o no tener listas en cada uno de sus componentes, el resultado debe de ser una lista de un sólo nivel de anidación.

Conceptos a estudiar:

Iteración de listas

En este caso se itera por todos los elementos que aparecen en el parámetro lst. Estos elementos pueden ser elementos simples o elementos anidados en forma de listas.

>>> for pos, elem in enumerate([1, ['pepe'], ['Juan', [['Ana']]]]):
...     print(f'{pos} -> {elem}')
...
0 -> 1
1 -> ['pepe']
2 -> ['Juan', [['Ana']]]

Extensión de listas en python

En Python existen dos formas de extender una lista, usando el método append y el método extend.

El método append permite extender una lista añadiendo un único elemento, y el método extend permite añadir muchos elementos (iteradores) de una vez.

>>> lst = []
>>> lst2 = list(range(7))
>>> lst2
[0, 1, 2, 3, 4, 5, 6]
>>> lst.append(78)
>>> lst
[78]
>>> lst.extend(lst2)
>>> lst
[78, 0, 1, 2, 3, 4, 5, 6]

Comprobación de tipos en Python

Para poder detectar una lista anidada, se comprueba si la variable a analizar es del tipo lista haciendo uso de la función isinstance. Análogamente se podría comparar utilizando type.

>>> for pos, elem in enumerate([1, ['pepe'], ['Juan', [['Ana']]]]):
...     print(f'{pos} -> {elem} - {type(elem)} - {isinstance(elem, list)}')
...
0 -> 1 - <class 'int'> - False
1 -> ['pepe'] - <class 'list'> - True
2 -> ['Juan', [['Ana']]] - <class 'list'> - True

El primer elemento ya es un elemento simple, pero en las posiciones 1 y 2 de la lista, se encuentran otras listas.

Una solución parcial al problema para aplanar cualquier lista sería extraer los elementos de la lista cuando se encuentre un elemento tipo lista, veamos el resultado:

>>> def aplanar_1_nivel(lst):
...     ret = []
...     for elem in lst:
...         if isinstance(elem, list):
...             ret.extend(elem)
...         else:
...             ret.append(elem)
...     return ret
...
>>> print(aplanar_1_nivel([1, ['pepe'], ['Juan', [['Ana']]]]))
[1, 'pepe', 'Juan', [['Ana']]]

Como podemos ver en esta solución parcial, los elementos resultantes son casi una lista plana, salvo los elementos que había en la posición original 2, dado que tienen un nivel de anidamiento de 3, y ahora se han convertido en anidamiento de nivel 2.

Por lo tanto, una solución válida podría ser llamar más veces a la función aplanar_1_nivel hasta no detectar que algún elemento es una lista:

>>> def aplanador_iterativo(lst):
...     while any([isinstance(x, list) for x in lst]):
...         lst = aplanar_1_nivel(lst)
...     return lst
...
>>> print(aplanador_iterativo([1, ['pepe'], ['Juan', [['Ana']]]]))
[1, 'pepe', 'Juan', 'Ana']

La forma de comprobar si existe algún elemento tipo lista en una línea se hace creando una lista por comprensión y haciendo uso de la función any, la cual será verdadero si alguno de sus valores son verdaderos.

any([isinstance(x, list) for x in lst])

Como se puede ver, la solución es válida pero cada vez que se encuentra un elemento tipo lista, hay que volver a evaluar todos los elementos y se va eliminando de 1 nivel en 1 nivel las anidaciones.

Si por ejemplo el último elemento de la lista original tuviera una anidación de nivel m, habría que evaluar la longitud de la lista (n) m veces, lo que hace que esta solución no sea óptima.

Llamadas recursivas

Python soporta gran parte de la programación funcional y una de sus principales características es la opción de usar llamadas recursivas.

Las llamadas recursivas son llamadas que se hacen en una función llamandose a sí misma. (no te asustes, es más fácil de lo que parece :D)

Si sabemos que tenemos una función que devuelve la forma no-anidada de una lista de valores, se podría añadir utilizando extend a cualquier lista, por lo que la lista original seguiria siendo no-anidada.

Pues con ese concepto tan simple, se puede crear la solución recursiva y elegante de este problema:

def flatter(lst):
    ret = []
    for elem in lst:
        if isinstance(elem, list):
            ret.extend(flatter(elem))  # <- llamada recursiva
        else:
            ret.append(elem)
    return ret

La idea tras esta solución al problema es que si el elemento es un elemento simple, se añade a la lista, y si es un elemento tipo lista, se aplica la misma función y se extiende la lista actual con lo que devuelva esa función.

Diferentes contextos de ejecución

Veamos cómo se ejecuta el código de ejemplo para entender mejor la solución. Se verá como van cambiando los contextos de cada llamada y sus variables internas:

# lst = [1, ['pepe'], ['Juan', [['Ana']]]]
def flatter(lst):
    ret = []
    for elem in lst:
        # elem = 1
        if isinstance(elem, list):
            ret.extend(flatter(elem))
        else:
            ret.append(elem)
            # ret = [1]
    return ret
# lst = [1, ['pepe'], ['Juan', [['Ana']]]]
def flatter(lst):
    ret = []
    for elem in lst:
        # elem = ['pepe']
        if isinstance(elem, list):
            ret.extend(flatter(elem))
            # resultado recursivo ['pepe']
            # ret = [1, 'pepe']
        else:
            ret.append(elem)
    return ret
# lst = [1, ['pepe'], ['Juan', [['Ana']]]]
def flatter(lst):
    ret = []
    for elem in lst:
        # elem = ['Juan', [['Ana']]
        if isinstance(elem, list):
            ret.extend(flatter(elem))
            # resultado recursivo ['Juan', 'Ana']
            # ret = [1, 'pepe', 'Juan', 'Ana']
        else:
            ret.append(elem)
    return ret

Como se puede ver la solución es simple, pero ¿qué ocurre en los contextos de las llamadas recursivas?

# lst = ['pepe']
def flatter(lst):
    ret = []
    for elem in lst:
        # elem = 'Pepe'
        if isinstance(elem, list):
            ret.extend(flatter(elem))
        else:
            ret.append(elem)
            # ret = ['Pepe']
    return ret
# lst = ['Juan', [['Ana']]]
def flatter(lst):
    ret = []
    for elem in lst:
        # elem = 'Juan'
        if isinstance(elem, list):
            ret.extend(flatter(elem))
        else:
            ret.append(elem)
            # ret = ['Juan']
    return ret
# lst = ['Juan', [['Ana']]]
def flatter(lst):
    ret = []
    for elem in lst:
        # elem = [['Ana']]
        if isinstance(elem, list):
            ret.extend(flatter(elem))
            # ret = ['Juan', 'Ana']
        else:
            ret.append(elem)
    return ret
# lst = [['Ana']]
def flatter(lst):
    ret = []
    for elem in lst:
        # elem = ['Ana']
        if isinstance(elem, list):
            ret.extend(flatter(elem))
            # ret = ['Ana']
        else:
            ret.append(elem)
    return ret
# lst = ['Ana']
def flatter(lst):
    ret = []
    for elem in lst:
        # elem = 'Ana'
        if isinstance(elem, list):
            ret.extend(flatter(elem))
        else:
            ret.append(elem)
            # ret = ['Ana']
    return ret

Como se puede ver, gracias a la recursión, la complejidad del problema se convierte en lineal. No hay necesidad de computar varias veces los mismos elementos ni hacer comprobaciones extra.

Sin embargo, hay que tener en cuenta que la recursión en Python no es infinita, sino que tiene un límite de 1000 llamadas recursivas anidadas, y que si se alcanza no se podrá ejecutar el programa.

Solución

Por tanto la solución correcta es la A:

A) [1, ‘pepe’, ‘Juan’, ‘Ana’]


Practica Python con PyQuizzes

En la sección de PyQuizzes puedes encontrar ejercicios prácticos explicados pormenorizado para mejorar tus habilidades como pythonista. ¡No te los pierdas!


Tutorial Python online

Aprender Python de forma gratuita siguiendo las secciones del tutorial de Python.


Libros recomendados para aprender Python

Estos son los libros que pueden ayudarte a aprender Python, aprender a programar, tipos de datos, algoritmia y mucho más.

Disponible en:

Compartir

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Información básica sobre protección de datos Ver más

  • Responsable Oscar Ramirez.
  • Finalidad Moderar los comentarios. Responder las consultas.
  • Legitimación Su consentimiento.
  • Destinatarios  ionos.
  • Derechos Acceder, rectificar y suprimir los datos.

Publicar un comentario