Secuencias y algoritmos aplicados

1. Generalidades

Una secuencia es un contenedor de objetos (que no son, necesariamente, únicos) que disponen de una relación de orden. Esto significa que los objetos pueden ser de cualquier tipo, y que se almacenan en un orden preciso. Varios objetos pueden, de este modo, estar incluidos varias veces en la misma secuencia, en posiciones diferentes.

Se distinguen dos tipos de secuencias: aquellas modificables o mutables, como las listas, y aquellas no modificables o inmutables, las n-tuplas o tuple en inglés.

Las primeras se utilizan para gestionar una secuencia de objetos que está destinada a «vivir», es decir, a modificarse de manera regular; las segundas se utilizan para agrupar datos, cuando los valores tienen un sentido más amplio que, simplemente, una sucesión de objetos ordenados, o también por motivos de rendimiento. La conservación de la semántica requiere que el objeto no pueda modificarse.

De este modo, cuando una función o un método devuelven varios valores, devuelven, en realidad, una n-tupla de valores:

>>> def test(): 
...     return 1, 2, 3 
...  
>>> test() 
(1, 2, 3) 
>>> a, b, c = test() 
>>> a 
1  
>>> b 
2  
>>> c  
3 

Para expresar, por ejemplo, las coordenadas de un punto en el plano o en el espacio, la n-tupla se utiliza con mayor frecuencia que la lista, pues tiene un sentido más fuerte:

>>> o=(0,0) 
>>> p=(1,6) 

Es posible trabajar con listas desde la programación orientada a objetos, aunque también utilizando programación funcional. Son una herramienta particularmente potente. Trabajar con las n-tuplas permite responder a otros objetivos, y se realiza a menudo sin darse cuenta, pues es un elemento indispensable del lenguaje.

No obstante, ambos tipos de datos tienen mucho en común, y los puntos para pasar de uno a otro permiten resolver todas las problemáticas.

El desarrollador debe tener precaución de no utilizar siempre el mismo tipo, sino buscar y contextualizar sus desarrollos para sacar el mejor provecho.

2. Las listas

Una lista es un conjunto modificable ordenado no desplegado de objetos Python. Dicho de otro modo, una lista que contiene de cero a varios objetos Python -con los métodos...

1. Definición de índice de un objeto y sus ocurrencias

El índice (index en inglés) es el número correspondiente al lugar que ocupa un objeto en la secuencia, partiendo de su inicio y siguiendo la relación de orden.

Puede obtenerse, simplemente, utilizando el método index, pasándole como parámetro el objeto deseado:

>>> l = [42, 74, 34]  
>>> l. index(34)  
2 

Si se solicita el índice de un objeto que no está presente, se obtiene una excepción:

>>> l.index(13)  
Traceback (most recent call last):  
File "<stdin>", line 1, in <module>  
ValueError: 13 is not in list 

Si un objeto está presente varias veces en una lista, se utiliza el segundo parámetro del método índice, que no es el número de la ocurrencia, sino el rango a partir del que se desea buscar:

>>> l = [42, 74, 34, 42, 51]  
>>> l.index(42, 0)  
0  
>>> l.index(42, 1)  
3  
>>> l.index(42, 2)  
3  
>>> l.index(42, 3)  
3  
>>> l.index(42, 4)  
Traceback (most recent call last):  
File "<stdin>", line 1, in <module>  
ValueError: 42 is not in list 

He aquí cómo encontrar, de manera sencilla, los índices de todas las ocurrencias:

>>> def indices(l, o, i=-1):  
...     while 1:  
...         try:  
...             i=l.index(o, i+1)  
...         except:  
...             return  
...         yield i  
...   
>>> for i in indices(l, 42):  
...     print(i)  
...   
0  
3 

También es posible contar el número de ocurrencias de un objeto:

>>> l.count(42) 
2 

2. Utilizar el índice para recorrer la secuencia

Es posible recuperar los elementos apuntándolos mediante su índice:

>>> l = [42, 74, 34] 
>>> l[0]  
42  
>>> l[1]  
74  
>>> l[2]  
34  ...

1. Operador +

El operador + tiene un sentido particular para las secuencias: la concatenación.

Los dos operadores deben ser, obligatoriamente, homogéneos:

>>> [1, 2]+(3, 4)  
Traceback (most recent call last):  
File "<stdin>", line 1, in <module>  
TypeError: can only concatenate list (not "tuple") to list  
>>> (1, 2)+[3, 4]  
Traceback (most recent call last):  
File "<stdin>", line 1, in <module>  
TypeError: can only concatenate tuple (not "list") to tuple 

El resultado del uso del operador + sobre dos secuencias es una secuencia que contiene el conjunto de elementos del operando de la izquierda, en orden, seguido del conjunto del de la derecha, en orden. La relación de orden se conserva:

>>> [1, 2]+[3, 4]  
[1, 2, 3, 4] 

El operador + se conecta con el método __add__ de la lista. Como los dos operandos son, necesariamente, homogéneos, no es preciso tener un método __radd__, presente cuando el operando de la izquierda no posee __add__. Esto permite sobrecargar el operador simplemente para darle otro significado.

Un ejemplo clásico consiste en modificar el significado del operador para aplicarlo en todos los miembros de la secuencia:

>>> class test(list):  
...     HETEROGENE_ERROR='can only concatenate test (not "%s") to test'  
...     def __add__(self, other):  
...         if not isinstance(other, test):  
...             raise TypeError(test.HETEROGENE_ERROR % type(other))  
...         result=test([0]*max(len(self), len(other)))  
...         for l in [self, other]:  
...             for i, o in enumerate(l):  
...                 result[i]+=o  
...         return result  
...   
>>> a=test([1, 2, 3, 4])  
>>> b=test([10, 20])  
>>> a+b  
[11, 22, 3, 4]  
>>> b+a  
[11, 22, 3, 4] 

Se habría podido realizar la misma operación sobre cadenas incluyendo cadenas vacías en lugar...

1. Agregar elementos a una lista y a una n-tupla

No es posible agregar un nuevo objeto a la lista utilizando un índice para una lista o utilizando el operador corchete sin argumentos, sintaxis que sí existe en otros lenguajes como, por ejemplo, PHP:

>>> l 
[42, 74, 34] 
>>> l[3] = 42 
Traceback (most recent call last): 
File "<stdin>", line 1, in <module> 
IndexError: list assignment index out of range 
>>> l[] = 42 
File "<stdin>", line 1 
l[] = 42 
 ^ 
SyntaxError: invalid syntax 

Para agregar un nuevo elemento a una lista, es preciso utilizar los métodos clásicos de la lista.

El método append agrega un elemento al final de la lista:

>>> l = [1, 2, 3]  
>>> l.append(4)  
>>> l  
[1, 2, 3, 4] 

El método insert agrega un elemento, precisando su índice. He aquí cómo agregar un objeto al inicio de la lista, por ejemplo:

>>> l = [1, 2, 3]  
>>> l.insert(0, 4)  
>>> l  
[4, 1, 2, 3] 

Como con los demás métodos, el uso del índice negativo sí está permitido:

>>> l.insert(-2, 5)  
>>> l  
[4, 1, 5, 2, 3] 

El objeto entero 5 se agrega dos posiciones antes del final, es decir, en la tercera posición de la lista de 4 elementos, o en el índice 2.

Estos métodos son los únicos que permiten agregar un objeto a una lista utilizando procesamientos unitarios.

No está permitido utilizar slices para agregar varios valores:

>>> l.insert(slice(1, 2), [1])  
Traceback (most recent call last):  
File "<stdin>", line 1, in <module>  
TypeError: 'slice' object cannot be interpreted as an integer 

Existen otros medios para agregar contenido a una lista, en particular elementos que provienen de otras secuencias.

De este modo, el método extend permite agregar a una lista el contenido de una segunda lista:

>>> l = [1, 2, 3]  
>>> l.extend([5, 4, 3])  
>>> l  
[1, 2, 3, 5, 4, 3] 

Los elementos de la segunda lista se agregan al final de la primera conservando el orden: ambas listas se concatenan. No existe ninguna noción...

1. Operaciones de conjunto

He aquí tres operaciones de conjunto sobre los miembros de la lista que ya se han visto en el capítulo Números, booleanos y algoritmos aplicados, sección Operaciones matemáticas n-arias:

>>> l = [1, 2, 3]  
>>> max(l)  
3  
>>> min(l)  
1  
>>> sum(l)  
6 

Estas operaciones pueden utilizarse únicamente para objetos que dispongan de una relación de orden, en el caso de las dos primeras, o que puedan agregarse entre sí, para la suma.

Además, todos los objetos de Python tienen un valor booleano, como hemos visto en el capítulo anterior. Supongamos que tenemos tres listas declaradas de la siguiente manera:

>>> l1 = [1, 2, 3]  
>>> l2 = [0, 1]  
>>> l3 = [0, ''] 

Es, por tanto, posible saber si todos los elementos de la lista son verdaderos:

>>> all(l1)  
True  
>>> all(l2)  
False  
>>> all(l3)  
False 

También es posible saber si al menos un miembro de la lista es verdadero:

>>> any(l1)  
True  
>>> any(l2)  
True  
>>> any(l3)  
False 

Y, por supuesto, esto puede utilizarse de manera combinada con la palabra clave not, lo que permite obtener la respuesta a las preguntas «¿algún elemento es verdadero?»:

>>> not any(l3)  
True  
>>> not any(l2)  
False  
>>> not any(l1)  
False 

Y «¿al menos un elemento es falso?»:

>>> not all(l3)  
True  
>>> not all(l2)  
True  
>>> not all(l1)  
False 

2. Pivotar una secuencia

La primitiva zip es una de las particularidades de Python que permite simplificar enormemente la manipulación cruzada de datos:

>>> zip(l)  
[(1,), (2,), (3,)]  
>>> zip([1, 2, 3], [1, 4, 9], ["a", "b", "c"])  
[(1, 1, 'a'), (2, 4, 'b'), (3, 9, 'c')] 

El resultado es una lista de n-tuplas, aunque es sencillo obtener únicamente listas o n-tuplas:

>>> [list(a) for a in zip([1, 2, 3], [1, 4, 9], ["a"...

1. Lista de enteros

La idea es controlar los datos de la lista de manera que se pueda asegurar que no contiene más que números (enteros o de coma flotante):

class intlist(list):  
   """Lista de números"""  
  
   __types__ = [int, float]  
  
   def __init__(self, *args, **kwargs):  
           """Sobrecarga genérica del constructor"""  
           list.__init__(self, *args, **kwargs)  
           for index, value in enumerate(self):  
                  if type(value) not in self.__types__:  
                         raise TypeError("el objeto %s de índice %s de 
la secuencia no es un número" % (value, index))  
  
   def append(self, value):  
          """Sobrecarga del método para agregar elementos al final de 
la lista""" 
           if type(value) not in self.__types__: 
                 raise TypeError("%s no es un número" % value) 
           list.append(self, value) 
 
    def insert(self, index, value): 
           """Sobrecarga del método para agregar elementos en un índice 
determinado""" 
           if type(value) not in self.__types__: 
                 raise TypeError("%s no es un número" % value) 
           list.insert(self, index, value) 
 
    def extend(self, seq): 
           """Sobrecarga del método de modificación de varios elementos""" 
          for index, value in enumerate(seq): 
               ...