Programmation Python/Ensembles
Définition
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. A titre d'exemple, les scalaires comme les entiers, flottants, tuples, et chaines 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
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])
Ajout par copie d'un autre ensemble :
>>> s2 = s.copy()
>>> s2
set([32, 9, 12, 14, 54, 26])
Recherche de membre
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
Il existe quatre fonctions pour retirer des membres à un ensemble :
- "pop" : retire un membre non précisé.
- "remove" : retire le membre existant précisé.
- "discard" : retire un membre précisé.
- "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
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
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
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])
Union
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
É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
É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
Depuis Python 2.6, les fonctions vues précédemment acceptent plus de deux arguments :
- .intersection()
- .union()
- .symmetric_difference()
- .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
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
- Créer un set {'cat', 1, 2, 3}, appelé "s".
- Créer un set {'c', 'a', 't', '1', '2', '3'}.
- Créer un frozen set {'cat', 1, 2, 3}, appelé "fs".
- Créer un set contenant {frozenset({'cat', 2, 3, 1})}.
Références
- Python Tutorial, section "Data Structures", subsection "Sets" -- python.org
- Python Library Reference on Set Types -- python.org
- PEP 218 -- Adding a Built-In Set Object Type, python.org, a nice concise overview of the set type