Python Quiz 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.
- Extensión de listas.
- Comprobación de tipos.
- Llamadas recursivas.
- Diferentes contextos de ejecución.
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'> - TrueEl 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 retLa 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 retComo 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 retComo 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.
