Ensembles et algorithmes appliqués

1. Définition d’un ensemble

Un ensemble est une collection non ordonnée d’objets uniques. Il n’y a donc pas de relation d’ordre et il est impossible de trouver deux éléments identiques. Il s’agit purement et simplement d’un ensemble, au sens mathématique du terme.

Un ensemble est à différencier d’une séquence (liste ou n-uplets) parce que son utilisation est radicalement différente alors que les différences entre une liste et un n-uplet sont d’ordre sémantique et technique.

Il existe deux types d’ensembles, les ensembles modifiables (set) et les ensembles non modifiables (frozenset). La différence au niveau technique est exactement du même ordre que celle entre les listes et les n-uplets.+

Par contre, au niveau sémantique, il n’y a pas de différences entre un set et un frozenset - alors qu’il y en a entre une liste et un n-uplet - les deux étant utilisés pour représenter le même type de données, ils ont la même signification.

Les ponts vus entre n-uplets, liste et itérateurs fonctionnent également avec les ensembles. Il est possible d’en construire un à partir d’une liste, d’un tuple ou d’autres séquences :

>>> set([1, 2, 3]) 
{1, 2, 3} 

On voit d’ailleurs dans la réponse de la console la nouvelle représentation d’un ensemble :

>>> {1, 2, 3} 
{1, 2, 3} 

Ceci ne doit pas être confondu avec un dictionnaire :

>>> {1:1, 2:2, 3:3} 
{1: 1, 2: 2, 3: 3} 

La représentation d’un ensemble vide passe par l’utilisation du constructeur car l’utilisation des accolades sans valeurs donne un dictionnaire :

>>> type({}) ...

1. Opérateurs pour un ensemble à partir de deux autres

Il faut rappeler la caractéristique principale d’un ensemble, pas de doublons :

>>> s1 = {1, 2, 3, 3} 
>>> s1 
{1, 2, 3} 

Ainsi, il est possible de :

>>> 3 in s1 
True 

>>> s2 = {5, 4, 3} 
>>> s1 - s2 
{1, 2} 

>>> s1 | s2 
{1, 2, 3, 4, 5} 

>>> s1 & s2 
{3} 

>>> s1 ^ s2 
{1, 2, 4, 5} 

Une addition pourrait s’entendre comme en mathématique, c’est-à-dire les objets du premier ensemble ajoutés aux objets du second ensemble moins les objets appartenant à l’intersection des deux ensembles, puisqu’il ne faut pas de doublons.

Étant donné que l’ensemble reste par nature un ensemble, l’addition est ici forcément la même chose que l’union, car les doublons sont automatiquement supprimés. On pourrait l’ajouter :

>>> class myset(set): 
...     __add__ = set.__or__ 
...  
>>> a, b = myset({1, 2, 3}), myset({5, 4, 3}) 
>>> a+b ...

1. Ajouter un élément

Ces méthodes ne sont disponibles que pour l’ensemble modifiable set et non pour frozenset. La première d’entre elles est add :

>>> s={1, 2, 3} 
>>> s.add(4) 
>>> s 
{1, 2, 3, 4} 
>>> s.add(1) 
>>> s 
{1, 2, 3, 4} 

Si la valeur est présente dans l’ensemble, celui-ci n’est pas modifié (l’ajout d’un élément déjà présent n’entraîne pas d’erreurs).

L’ajout d’un élément est équivalent à l’union avec un ensemble ne contenant que cet élément :

>>> s|={5} 
>>> s 
{1, 2, 3, 4, 5} 

2. Supprimer un élément

Il y a deux moyens de supprimer un élément d’un ensemble. Tout d’abord, la méthode remove qui porte le même nom que pour une liste, mais qui ne prend qu’un seul argument, puisqu’il n’y a qu’une seule occurrence de chaque objet :

>>> s.remove(5) 

Si la valeur que l’on demande à retirer n’est pas présente dans l’ensemble, une exception est levée (comportement similaire à la liste, même si le type de l’exception est différent) :

>>> s.remove(8) 
Traceback (most recent call last): 
File "<stdin>", line 1, in <module> 
KeyError: 8 
>>> [].remove(1) 
Traceback (most recent call last): 
File "<stdin>", line 1, in <module> 
ValueError: list.remove(x): x not in list 

Un autre moyen de supprimer est l’utilisation de la méthode discard qui ne lève pas d’exception. Elle permet le même...