Programmation Python/Ensembles

Définition

modifier

En Python, les ensembles sont définis par le mot "set()"[1] depuis Python 2.3, d'abord en important le module du même nom, puis depuis nativement Python 2.6, avec "frozenset()".

Un ensemble est une collection non ordonnée d'objets, contrairement aux séquences comme les listes et les tuples dans lesquels chaque élément est indexé. Un ensemble ne peut pas contenir de doublon : on ne peut y trouver des éléments que zéro ou une fois. Tous les membres d'un ensemble doivent être hachable, comme les clés des dictionnaires. À titre d'exemple, les scalaires comme les entiers, flottants, tuples, et chaînes sont hachables ; par contre les dictionnaires, listes, et ensembles ne le sont pas.

Exemple :

set1 = set()                    # Nouvel ensemble vide
set1.add("cat")                 # Ajout d'un membre
set1.update(["dog", "mouse"])   # Ajout de plusieurs membres
if "cat" in set1:               # Recherche d'un membre
  set1.remove("cat")            # Retrait d'un membre
#set1.remove("elephant")        - Erreur de retrait d'un membre introuvable
set1.discard("elephant")        # Aucune erreur de retrait d'un membre introuvable

print(set1)                     # Affichage d'un ensemble
for item in set1:               # Itération pour chaque élément
  print(item)
print("Item count:", len(set1)) # Compte des éléments

#1stitem = set1[0]              # Erreur d'index introuvable
isempty = len(set1) == 0        # Test si l'ensemble est vide
set1 = set(["cat", "dog"])      # Initialisation de l'ensemble depuis une liste de membre
set2 = set(["dog", "mouse"])
set3 = set1 & set2              # Intersection
set4 = set1 | set2              # Union
set5 = set1 - set3              # Différence
set6 = set1 ^ set2              # Différence symétrique
issubset = set1 <= set2         # Test de sous-ensemble
issuperset = set1 >= set2       # Test de sur-ensemble
set7 = set1.copy()              # Copie d'un ensemble
set7.remove("cat")
set8 = set1.copy()
set8.clear()                    # Effacement d'un ensemble
print(set1, set2, set3, set4, set5, set6, set7, set8, issubset, issuperset)

Construction d'ensembles

modifier

Une première méthode consiste à fournir un objet séquentiel en paramètre :

>>> set([0, 1, 2, 3])
set([0, 1, 2, 3])

>>> set("obtuse")
set(['b', 'e', 'o', 's', 'u', 't'])

Ajout de chaque membre un par un :

>>> s = set([12, 26, 54])
>>> s.add(32)
>>> s
set([32, 26, 12, 54])

Ajout de groupes de membres :

>>> s.update([26, 12, 9, 14])
>>> s
set([32, 9, 12, 14, 54, 26])
 si on ajoute un doublon avec "add()" ou "update()", cela n'a aucun effet.

Ajout par copie d'un autre ensemble :

>>> s2 = s.copy()
>>> s2
set([32, 9, 12, 14, 54, 26])

Recherche de membre

modifier

Pour chercher si un élément existe dans un ensemble, on utilise "in" :

>>> 32 in s
True
>>> 6 in s
False
>>> 6 not in s
True

Si un sous-ensemble existe dans un ensemble, c'est "issubset()" :

>>> s.issubset(set([32, 8, 9, 12, 14, -4, 54, 26, 19]))
True

Si un sur-ensemble contient un ensemble, c'est "issuperset()" :

>>> s.issuperset(set([9, 12]))
True

# Équivalent à :
>>> s.issuperset([9, 12])

# Équivalent à :
>>> s >= [9, 12]

Retrait de membre

modifier

Il existe quatre fonctions pour retirer des membres à un ensemble :

  1. "pop" : retire un membre non précisé.
  2. "remove" : retire le membre existant précisé.
  3. "discard" : retire un membre précisé.
  4. "clear" : retire tous les éléments.
>>> s = set([1,2,3,4,5,6])
>>> s.pop()
1
>>> s
set([2,3,4,5,6])

>>> s.remove(3)
>>> s
set([2,4,5,6])

>>> s.remove(9)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
KeyError: 9

>>> s.clear()
>>> s
set([])

Itération des ensembles

modifier

Les éléments n'étant pas ordonnés, il n'y a qu'une boucle possible :

>>> s = set("blerg")
>>> for n in s:
...     print n,
...
r b e l g

Opérations sur les ensembles

modifier

Python offre les mêmes opérations sur les ensembles qu'en mathématiques, applicables par soit par des opérateurs, soit par des fonctions équivalentes. Les fonctions dont le nom se termine par _update modifie l'ensemble qui devient le résultat et ne retourne rien au lieu de retourner le résultat.

Intersection

modifier
 
L'intersection des deux cercles apparaît en rouge.

Les éléments communs à deux ensembles.

>>> s1 = set([4, 6, 9])
>>> s2 = set([1, 6, 8])
>>> s1.intersection(s2)
set([6])
>>> s1 & s2
set([6])

>>> s1.intersection_update(s2)
>>> s1
set([6])
 
L'union des deux cercles apparaît en rouge.

Somme des éléments de deux ensembles.

>>> s1 = set([4, 6, 9])
>>> s2 = set([1, 6, 8])
>>> s1.union(s2)
set([1, 4, 6, 8, 9])
>>> s1 | s2
set([1, 4, 6, 8, 9])

Différence symétrique

modifier
 
La différence symétrique des deux cercles apparaît en rouge.

Éléments contenu dans un seul ensemble à la fois, parmi deux. autrement  : [ l'union des deux #set] -[l'intersection]

>>> s1 = set([4, 6, 9])
>>> s2 = set([1, 6, 8])
>>> s1.symmetric_difference(s2)
set([8, 1, 4, 9])
>>> s1 ^ s2
set([8, 1, 4, 9])

>>> s1.symmetric_difference_update(s2)
>>> s1
set([8, 1, 4, 9])

Différence

modifier
 
La différence asymétrique entre les deux cercles apparaît en rouge.

Éléments non contenu dans un des deux ensembles.

>>> s1 = set([4, 6, 9])
>>> s2 = set([1, 6, 8])
>>> s1.difference(s2)
set([9, 4])
>>> s1 - s2
set([9, 4])

>>> s1.difference_update(s2)
>>> s1
set([9, 4])

Opérations non binaires

modifier

Depuis Python 2.6, les fonctions vues précédemment acceptent plus de deux arguments :

  1. .intersection()
  2. .union()
  3. .symmetric_difference()
  4. .difference().

Un appel à plus de deux arguments est équivalent à des appels enchaînés à deux arguments, ou un argument dans le cas d'un appel de méthode sur une instance.

Exemple :

>>> s1 = set([3, 6, 7, 9])
>>> s2 = set([6, 7, 9, 10])
>>> s3 = set([7, 9, 10, 11])
>>> set.intersection(s1, s2, s3)
set([9, 7])
>>> set.intersection(s1, s2).intersection(s3)
set([9, 7])
>>> s1.intersection(s2).intersection(s3)
set([9, 7])
>>> s1.intersection(s2,s3)
set([9, 7])

frozenset

modifier

Un "frozenset" (ensemble figé) se comporte comme un ensemble, sauf qu'il est immutable, c'est-à-dire qu'une fois créé, on ne peut pas le mettre à jour. Il dispose donc des mêmes fonctions que le type "set", mais sans "add", "update", "pop", "remove", "discard" et "clear".

De plus, ils sont hachables, ce qui leur permet de faire partie d'ensembles.

>>> fs = frozenset([2, 3, 4])
>>> s1 = set([fs, 4, 5, 6])
>>> s1
set([4, frozenset([2, 3, 4]), 6, 5])
>>> fs.intersection(s1)
frozenset([4])

>>> fs.add(6)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'

Les instructions suivantes montrent que les méthodes modificatrices sont absentes de la classe frozenset :

>>> set(dir(set)) - set(dir(frozenset))
{'__iand__', 'pop', 'add', '__isub__', 'clear', '__ior__', 'discard', 'update', '__ixor__', 'intersection_update', 'difference_update', 'symmetric_difference_update', 'remove'}
>>> set(dir(frozenset)) - set(dir(set))
set()

Exercices

modifier
  1. Créer un set {'cat', 1, 2, 3}, appelé "s".
  2. Créer un set {'c', 'a', 't', '1', '2', '3'}.
  3. Créer un frozen set {'cat', 1, 2, 3}, appelé "fs".
  4. Créer un set contenant {frozenset({'cat', 2, 3, 1})}.

Références

modifier