Séquences et algorithmes appliqués

1. Généralités

Une séquence est un conteneur d’objets (qui ne sont pas forcément uniques) disposant d’une relation d’ordre. Cela signifie que les objets peuvent être de tout type, et qu’ils sont stockés dans un ordre précis. Plusieurs objets peuvent ainsi être plusieurs fois dans la même séquence, à des positions différentes.

On distingue deux types de séquences, celles modifiables ou mutables, les listes et celles non modifiables ou non mutables, les n-uplets ou tuple en anglais.

Les premières sont utilisées pour gérer une séquence d’objets qui est destinée à « vivre », c’est-à-dire à être modifiée régulièrement ; les secondes sont utilisées pour regrouper des données, lorsque les valeurs ont un sens plus large que simplement une succession d’objets ordonnés ou pour des raisons de performances. La conservation de la sémantique nécessite que l’objet ne puisse être modifié.

Ainsi, lorsqu’une fonction ou une méthode retourne plusieurs valeurs, elle retourne en réalité un n-uplet de valeurs :

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

Pour exprimer, par exemple, les coordonnées d’un point, dans le plan ou dans l’espace, le n-uplet est plus volontiers utilisé que la liste, car il a un sens plus fort :

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

Travailler avec les listes peut s’effectuer par la programmation objet, mais aussi par la programmation...

1. Définition de l’indice d’un objet et des occurrences

L’indice (index en anglais) est le numéro de l’emplacement d’un objet dans la séquence, en partant de son début et en suivant la relation d’ordre.

Il peut être obtenu simplement, par l’utilisation de la méthode index en y passant en argument l’objet souhaité :

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

Si l’indice d’un objet non présent est demandé, une exception est alors obtenue :

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

Si un objet est présent plusieurs fois dans une liste, le second paramètre de la méthode index est utilisé, qui n’est pas le numéro de l’occurrence, mais le rang à partir duquel chercher :

>>> 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 

Voici comment trouver simplement les indices de toutes les occurrences :

>>> 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 

Il est également possible de compter...

1. Opérateur +

L’opérateur + a une signification particulière pour la séquence : la concaténation.

Les deux opérandes doivent forcément être homogènes :

>>> [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 

Le résultat de l’utilisation de l’opérateur + sur de deux séquences est une séquence contenant l’ensemble des éléments de l’opérande de gauche, dans l’ordre, suivi de l’ensemble de ceux de droite, dans l’ordre. La relation d’ordre est donc conservée :

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

L’opérateur + se connecte à la méthode __add__ de la liste. Comme les deux opérandes sont forcément homogènes, il n’est pas nécessaire d’avoir une méthode __radd__ qui est présente lorsque l’opérande de gauche ne possède pas __add__. Ceci permet de surcharger l’opérateur simplement, pour lui donner une autre signification.

Un exemple classique en est de reporter la signification de l’opérateur sur tous les membres de la séquence :

>>> 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...

1. Ajouter des éléments dans une liste et un n-uplet

Il n’est pas possible d’ajouter un nouvel objet à la liste par l’utilisation d’un indice hors d’une liste ou par l’utilisation de l’opérateur crochet sans arguments, cette syntaxe existant dans d’autres langages tels que 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 

Pour ajouter un nouvel élément dans une liste, il faut alors se reporter sur les méthodes classiques de la liste.

La méthode append rajoute un élément en fin de liste :

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

La méthode insert rajoute un élément, en précisant son index. Voici comment ajouter un objet en début de liste, par exemple :

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

Comme pour les autres méthodes, l’utilisation de l’indice négatif est permise :

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

L’objet entier 5 est ajouté deux places avant la fin, soit à la troisième position de la liste à 4 éléments ou à l’index 2.

Ces méthodes sont les seules méthodes permettant de rajouter un objet à une liste par des traitements unitaires.

Il n’est pas permis d’utiliser des slices pour rajouter plusieurs valeurs :

>>> l.insert(slice(1, 2), [1]) 
Traceback (most recent call last): ...

1. Opérations d’ensemble

Voici trois opérations d’ensemble sur les membres de la liste déjà vues dans le chapitre Nombres, booléens et algorithmes appliqués - section Opérations mathématiques n-aires :

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

Ces opérations ne sont utilisables que pour des objets disposant d’une relation d’ordre, pour les deux premiers ou additionnables entre eux, pour la somme.

De plus, tous les objets Python ont une valeur booléenne, comme nous l’avons vu dans le chapitre précédent. Soit trois listes ainsi déclarées :

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

Il est donc possible de savoir si tous les éléments de la liste sont vrais :

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

Il est aussi possible de savoir si au moins un membre de la liste est vrai :

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

Et bien sûr, cela peut s’utiliser en combinaison avec le mot-clé not, permettant d’avoir la réponse aux questions « aucun élément n’est vrai » :

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

Et « Au moins un élément est faux » :

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

2. Pivoter une séquence

La primitive zip est une des particularités de Python qui permet de grandement simplifier la manipulation croisée...

1. Liste d’entiers

L’idée est de contrôler les données mises dans la liste de manière à s’assurer qu’elles ne contiennent que des nombres (entiers ou flottants) :

class intlist(list): 
   """Liste de nombres""" 
 
   __types__ = [int, float] 
 
    def __init__(self, *args, **kwargs): 
           """Surcharge générique du constructeur""" 
           list.__init__(self, *args, **kwargs) 
           for index, value in enumerate(self): 
                  if type(value) not in self.__types__: 
                         raise TypeError("l'objet %s d'index %s de  
la séquence n'est pas un nombre" % (value, index)) 
 
    def append(self, value): 
           """Surcharge de la méthode d'ajout d'éléments en fin de  
liste""" 
           if type(value) not in self.__types__: 
                 raise TypeError("%s n'est pas un nombre" % value) 
           list.append(self, value) 
 
    def insert(self, index, value): 
           """Surcharge de la méthode d'ajout d'éléments à un index 
donné""" 
           if type(value) not in self.__types__: 
   ...