Généralités sur les ensembles
La structure d’ensemble
Un ensemble est une structure de données de type conteneur et dont les éléments sont deux à deux distincts. Python dispose nativement d’une structure appelée set
qui implémente une structure d’ensemble. Voici un exemple :
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
|
- Ligne 1:
s
est un ensemble au sens du langage Python.
- Ligne 3: on observe que
s
a bien ses éléments deux à deux distincts.
Les ensembles en Python définissent un type, appelé set.
Un ensemble ressemble à une liste sauf que
- ses éléments ne sont jamais répétés,
- il n’existe pas d’ordre prédéfini de parcours de l’ensemble, tandis que pour une liste, l’ordre par défaut est donné par indices croissants.
A la différence des dictionnaires, les ensembles en Python ne préservent pas l’ordre d’insertion des éléments dans l’ensemble, voir cette discussion.
Ensemble littéral
Le moyen le plus immédiat de définir un ensemble est de lister tous ses éléments en les plaçant entre des accolades et séparés par des virgules, comme on le fait en mathématiques. Une telle expression définit ce qu’on appelle un ensemble littéral :
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
|
- Ligne 1 : par définition, le membre de droite de l’affectation est un ensemble littéral. Ses éléments figurent entre les accolades et, ici, sont des entiers.
Comme un ensemble ne contient que des éléments différents, si dans la liste entre accolades on place des éléments de même valeur, seul un exemplaire de cet élément est répertorié dans l’ensemble :
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
|
- Ligne 1 : des éléments identiques apparaissent dans la liste des éléments de l’ensemble
s
.
- Ligne 3 : on lit la liste des éléments distincts. Chaque élément qui était répété est pris en compte une seule fois.
Nombre d’éléments d’un ensemble
Un ensemble est un conteneur et il possède donc un certain nombre d’éléments. Le nombre d’éléments d’un ensemble s
est obtenu par appel à la fonction built-in len
:
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
n = len(s)
print(n)
|
- Lignes 2 et 6 : le nombre d’éléments de l’ensemble
s
. On observera qu’un élément présent plusieurs fois dans la liste initiale n’est compté qu’une seule fois.
Affichage d’un ensemble
Si s
est un ensemble non vide, l’affichage produit par print(s)
est l’expression d’un ensemble sous forme d’ensemble littéral :
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
|
Les éléments de l’ensemble apparaissent une fois et une seule, il n’y a jamais de doublons dans l’affichage. L’ordre d’affichage est non spécifié.
Création d’ensembles avec set
Il existe d’autres procédés de création d’ensemble que la syntaxe d’ensemble littéral. On peut construire un ensemble avec le type set
. Le processus est expliqué à l’exemple suivant :
| L = [65, 31, 12, 81, 81, 65, 81, 12]
s = set(L)
print(s)
|
- Ligne 1 : pour créer un ensemble formé à partir de certains éléments, on peut placer tous ses éléments dans une liste.
- Ligne 2 : on appelle ensuite le constructeur
set
sur cette liste. L’appel renvoie alors l’ensemble associé. Les éléments de la liste présents plusieurs fois ne sont pris en compte qu’une seule fois.
set
est appelé un constructeur puisqu’il permet de construire des objets d’une certaine catégorie, ici un ensemble.
Le constructeur set
permet de construire un ensemble à partir d’une liste. Les éléments distincts de la liste seront les éléments de l’ensemble.
Ensemble vide
Un ensemble peut être vide :
| s = set()
print(s)
print(len(s))
|
- Lignes 1 et 4 : observer la notation spécifique de l’ensemble vide
Un ensemble vide trouve son intérêt :
- on cherche à comparer un ensemble donné à l’ensemble vide
- l’ensemble vide peut être le conteneur de base d’un ensemble qui va grossir
Attention, la notation {}
ne doit pas être utilisée pour désigner l’ensemble vide.
Test d’appartenance à un ensemble
La possibilité de tester l’appartenance d’un objet à un ensemble est une propriété fondamentale d’un ensemble et qui en fait tout l’intérêt. On peut tester avec l’opérateur in
l’appartenance d’un objet donné à un ensemble donné :
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(42 in s)
print(42 not in s)
|
Un ensemble est une structure beaucoup plus efficace qu’une liste pour savoir si un objet appartient à un groupe d’éléments. Par exemple, si des objets sont rangés dans une liste L
de longueur \(n\), la recherche de l’appartenance d’un élément x
à L
peut nécessiter jusqu’à \(n\) comparaisons. En revanche, si les objets sont placés dans un ensemble, la nature de la structure de données qu’est un ensemble rend cette recherche efficace.
Type des éléments d’un ensemble
Les éléments d’un ensemble ne sont pas nécessairement de même type :
| s = {42, "orange", "rose", 42, 2038}
print(s)
|
| {'rose', 42, 'orange', 2038}
|
La documentation Python, ne mentionne aucune recommandation sur la nature hétérogène ou homogène des éléments d’un ensemble.
La nature hachable des éléments d’un ensemble
Les éléments d’un ensemble ne peuvent être quelconques : ils doivent appartenir à la catégorie des objets dit hachables. C’est le langage qui définit les objets qui sont hachables ou non. Par exemple, une liste n’est pas hachable et donc, un ensemble ne peut contenir aucune liste parmi ses éléments :
| s = {[42, 81, 10], 100}
print(s)
|
| TypeError: unhashable type: 'list'
|
Les objets suivants sont toujours hachables :
- les entiers,
- les chaînes de caractères,
- les tuples s’ils sont formés d’éléments eux-mêmes hachables.
Un élément de type set
n’est jamais hachable. On ne peut donc considérer un ensemble d’ensembles ni même un ensemble de listes.
Utiliser des tuples
Un tuple étant hachable (au moins en première approximation), on peut transformer l’exemple ci-dessus pour obtenir un ensemble valide en utilisant un tuple plutôt qu’une liste :
| s = {(42, 81, 10), 100}
print(s)
|
- Ligne 3 :
s
possède deux éléments : un entier et un tuple de trois entiers.
Ensemble élément d’un ensemble
Un ensemble de type set
n’étant pas hachable, il ne peut être élément d’un autre ensemble :
| a = set([4, 6])
b = set([5, 8])
c = set([1, 3])
s = set([a, b, c])
|
| TypeError: unhashable type: 'set'
|
Donc pas d’ensemble des parties d’un ensemble en Python comme cela existe en mathématiques …
Un ensemble est mutable
Un ensemble de type set
, de même qu’une liste, est un type mutable : un ensemble peut être modifié par complétion ou suppression d’éléments :
| a = set([4, 2, 1])
print(a)
a.remove(1)
print(a)
a.add(100)
print(a)
|
| {1, 2, 4}
{2, 4}
{100, 2, 4}
|
- Ligne 1 : l’ensemble
a
va être modifié
- Ligne 4 : un ensemble possède une méthode permettant de retirer un élément ; ici, on retire l’élément 1 à l’ensemble
a
- Ligne 7 : un ensemble possède une méthode permettant d’ajouter un élément ; ici, on adjoint l’élément 100 à l’ensemble
a
.
Parcours d’un ensemble
Un ensemble est un itérable et en particulier, on peut parcourir un ensemble avec une boucle for
:
| s = {65, 31, 12, 81, 81, 65, 81, 12}
for x in s:
print(x)
|
À la différence d’une liste, un ensemble n’est pas une séquence qui posséderait un ordre canonique de parcours. L’ordre de parcours d’un ensemble est non spécifié par le langage.
Ensembles en compréhension
Il existe un analogue des listes en compréhension pour les ensembles : les ensembles en compréhension.
| A={10 * i for i in range(1,11)}
print(A)
|
| {100, 70, 40, 10, 80, 50, 20, 90, 60, 30}
|
- Ligne 1 :
A
est défini par un ensemble en compréhension.
La syntaxe de l’ensemble en compréhension est calquée sur celle des listes en compréhension. En particulier, il est possible d’utiliser une clause if
:
| A={10 * i for i in range(1,11) if i % 3 == 0}
print(A)
|
Valeur booléenne d’un ensemble
On sait qu’une liste n’ayant aucun élément a une valeur booléenne False
. De même, l’ensemble vide a une valeur booléenne False
:
| empty = set()
print(bool(empty))
non_empty = set([42, 2020])
print(bool(non_empty))
|
En revanche, un ensemble non vide a une valeur booléenne True
.
Ensembles construits sur un itérable
On peut construire un ensemble à partir d’une liste :
| L = [65, 31, 12, 81, 81, 65, 81, 12]
s = set(L)
|
mais en fait à partir de n’importe quel itérable comme une chaîne :
| s = "BANANA"
S = set(s)
print(S)
|
- Lignes 2 et 4 :
S
est l’ensemble dont les éléments sont les lettres distinctes de la chaîne s
: la chaîne s
est de longueur 6 mais l’ensemble S
est de longueur 3.
Les objets de type range(n)
sont aussi des itérables et permettent donc de créer des ensembles :
| r = range(10)
S = set(r)
print(S)
|
| {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
|
Doublons
Présence de doublons dans une liste
Comme un ensemble est une structure de données dont les éléments ne sont jamais répétés, un ensemble donne le moyen d’extraire les éléments distincts d’une liste. Un ensemble permet aussi de savoir si une liste L
admet des répétitions (ce qu’on appelle des « doublons ») :
| L = [65, 31, 12, 81, 81, 65, 81, 12]
print(L)
# L est-elle sans doublons ?
print(len(L) == len(set(L)))
print()
L = [65, 31, 12, 81]
print(L)
# L est-elle sans doublons ?
print(len(L) == len(set(L)))
|
| [65, 31, 12, 81, 81, 65, 81, 12]
False
[65, 31, 12, 81]
True
|
- Ligne 1: une liste qui contient des doublons, par exemple 81 (qui apparaît trois fois).
- Lignes 4 et 12 : ce test montre que L contient des doublons.
- Lignes 7 et 15 : L’ensemble défini par
L
est sans doublon.
Ainsi, on vient d’observer la technique du test de doublon : pour savoir si une liste L
de longueur n
contient des doublons il suffit de construire l’ensemble associé à L
et examiner si cet ensemble admet également n
éléments. Si ce n’est pas le cas, c’est que L
admet des doublons.
Conversion d’un ensemble en liste
A tout ensemble Python est associée une liste Python qui représente la liste des éléments de l’ensemble. Pour générer la liste associée à un ensemble on utilise le constructeur list
:
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
L = list(s)
print(L)
print(s)
|
| {81, 31, 12, 65}
[81, 31, 12, 65]
{81, 31, 12, 65}
|
- Lignes 3 et 7 : un ensemble peut être converti en liste avec le constructeur
list
: les éléments de l’ensemble sont rangés dans la liste dans un ordre indéterminé.
- Lignes 2, 5, 6 et 8 : convertir un ensemble en liste crée une liste et ne modifie pas l’ensemble.
Suppression des doublons d’une liste
On dispose d’une liste L
et on souhaite créer une nouvelle liste M
à partir des éléments de L
mais en sorte que la liste M
soit sans répétition. Par exemple, si
L = [65, 31, 12, 81, 81, 65, 81, 12]
alors M = [65, 12, 81, 31]
.
Voici comment on obtient la liste sans doublon :
| L = [65, 31, 12, 81, 81, 65, 81, 12]
print(L)
M = list(set(L))
print(M)
|
| [65, 31, 12, 81, 81, 65, 81, 12]
[65, 12, 81, 31]
|
On a converti la liste en ensemble et reconverti le résultat en liste.
Méthodes mutatrices
Les méthodes add
et update
d’un ensemble
On peut compléter un ensemble par ajout d’un élément :
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
z = s.add(42)
print(s)
print(z)
s.add(42)
print(s)
|
| {81, 31, 12, 65}
{81, 42, 31, 12, 65}
None
{81, 42, 31, 12, 65}
|
- Ligne 4 : on peut « ajouter » un élément à un ensemble avec la méthode
add
.
- Lignes 6 et 12 : la méthode
add
ne renvoie rien, elle se contente de modifier l’ensemble.
- Lignes 8-9 : il est possible d’ajouter un élément déjà présent : l’ensemble est alors inchangé.
Si on veut ajouter plusieurs éléments à un ensemble s
, on peut
- répéter l’insertion avec la méthode
s.add
comme plus haut ;
- utiliser la méthode
s.update
pour faire l’opération en une fois, comme expliqué ci-essous.
Si s
est un ensemble, la méthode s.update
permet même de compléter l’ensemble s
par les éléments d’un itérable t
, cet itérable n’étant pas forcément un ensemble, cela peut être une liste comme dans l’exemple ci-dessous :
s = {4, 5, 6}
t = [40, 50, 60, 70]
s.update(t)
print(s)
{4, 5, 6, 70, 40, 50, 60}
Noter que l’appel s.update(t)
modifie s
mais ne le renvoie pas (ça renvoie même None
).
Retirer un élément avec la méthode discard
Un appel s.discard(a)
retire l’élément a de l’ensemble s
si a
est présent dans s
et sinon, l’appel est sans effet :
| s = {65, 31, 12, 81, 81, 65, 81, 12}
z = s.discard(81)
print(s)
print(z)
s.discard(81)
print(s)
|
| {31, 12, 65}
None
{31, 12, 65}
|
- Ligne 1 : la méthode
discard
retire un élément s’il est présent dans un ensemble.
- Lignes 5 et 10 : la méthode
discard
ne retourne rien et se contente de modifier l’ensemble.
- Lignes 7 et 11 : il est possible de tenter de retirer un élément non présent dans l’ensemble. L’appel laisse l’ensemble inchangé.
Retirer un élément avec la méthode remove
La méthode remove
permet de retirer un élément donné d’un ensemble donné :
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
z = s.remove(81)
print(s)
print(z)
|
| {81, 31, 12, 65}
{31, 12, 65}
None
|
Si on tente de retirer avec la méthode remove
, un élément a
d’un ensemble s
qui ne contient pas a
, l’appel déclenche une erreur :
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
s.remove(42)
|
| {81, 31, 12, 65}
Traceback (most recent call last):
File "_.py", line 3, in <module>
s.remove(42)
KeyError: 42
|
- 42 n’est pas dans l’ensemble
s
.
La méthode pop
La méthode pop
retire un élément arbitraire d’un ensemble :
| s = {65, 31, 12, 81, 81, 65, 81, 12}
z = s.pop()
print(s)
print(z)
|
- Lignes 2, 4 et 6 : la méthode pop retire un élément arbitraire d’un ensemble
- Lignes 2 et 5 : la méthode
pop
renvoie l’élément qu’elle retire. La méthode pop
est la seule façon d’accéder à un élément d’un ensemble.
La méthode pop
retire un élément arbitraire et inconnu au moment de l’appel. En fait, la méthode pop
renvoie l’élément qu’elle retire de l’ensemble et l’usage essentiel de cette méthode est plutôt d’extraire un élément, a priori inconnu, d’un ensemble donné.
Méthode pop
et ensemble vide
Un appel de la méthode pop
sur l’ensemble vide entraîne la levée d’une exception :
| s = {42}
s.pop()
s.pop()
print(s)
|
| KeyError: 'pop from an empty set'
|
- Ligne 2 : on a retiré 42 de l’ensemble
s
, l’ensemble est donc vide
- Ligne 3 : on tente de retirer un élément d’un ensemble vide : le programme est interrompu (ligne 5)
Opérations entre ensembles
Panorama des opérations sur les ensembles
On peut faire les opérations mathématiques usuelles sur les ensembles.
Opérations de comparaison
- égalité : deux ensembles sont-ils égaux ?
- disjonction : deux ensembles n’ont-ils aucun élément commun ?
- contenance : un ensemble est-il contenu dans l’autre ?
La contenance admet deux syntaxes : opérateurs et méthodes.
Opérations binaires sur des ensembles
- l’intersection,
- la réunion
- la différence
- la différence symétrique
Les quatre opérations ci-dessus admettent deux syntaxes utilisant :
- soit un opérateur,
- soit une méthode.
Et en outre, chacune des quatre opérations ci-dessus peut être utilisée dans une version qui modifie un des deux ensembles, et là encore sous deux syntaxes (opérateur et méthode).
|
Intersection |
Réunion |
Différence |
Différence
symétrique |
opérateur |
& |
| |
- |
^ |
méthode |
intersection |
union |
difference |
symmetric_
difference |
opérateur
augmenté |
&= |
|= |
-= |
^= |
méthode
mutatrice |
intersection_
update |
update |
difference_
update |
symmetric_diff
erence_update |
Égalité d’ensembles
On dispose de deux ensembles A
et B
et on cherche à savoir si les ensembles A
et B
ont mêmes éléments ie si mathématiquement \(A = B\).
Pour comparer deux ensembles, on utilise les opérateurs ==
et !=
:
| s = {1, 2, 1, 3}
t = {2, 2, 1, 3, 3}
print(s)
print(t)
print(s == t)
print(s != t)
|
| {1, 2, 3}
{1, 2, 3}
True
False
|
Inclusion et contenance entre ensembles
Le tableau ci-dessous présente :
- les quatre opérateurs de comparaison, large ou stricte, entre ensembles
- les deux méthodes testant l’inclusion ou la contenance large.
Table: Opérateurs et méthodes de comparaison entre ensembles
Comparaison |
Notation
mathématique |
Opérateur
Python |
Méthode |
\(A\) est inclus
dans \(B\)
au sens
large |
\(A\subseteq B\) |
A <= B |
A.issubset(B) |
\(A\) contient
\(B\) au sens
large |
\(A\supseteq B\) |
A >= B |
A.issuperset(B) |
\(A\) est
strictement
inclus dans
\(B\) |
\(A\subsetneq B\) |
A < B |
|
\(A\) contient
strictement
\(B\) |
\(A\supsetneq B\) |
A > B |
|
Les appels de méthodes et les opérateurs renvoient des booléens.
Illustration avec les opérateurs
| A = {1, 2, 1, 3}
B = {0, 2, 2, 1, 3, 3}
print(A)
print(B)
print("A <= B","->", A <= B)
print("A < B","->", A < B)
print("A >= B","->", A >= B)
print("A > B","->", A >= B)
|
| {1, 2, 3}
{0, 1, 2, 3}
A <= B -> True
A < B -> True
A >= B -> False
A > B -> False
|
Illustration avec les méthodes
| A = {1, 2, 1, 3}
B = {0, 2, 2, 1, 3, 3}
print(A)
print(B)
print("A.issubset(B)","->", A.issubset(B))
print("A.issuperset(B)","->", A.issuperset(B))
|
| {1, 2, 3}
{0, 1, 2, 3}
A.issubset(B) -> True
A.issuperset(B) -> False
|
Ensembles disjoints
Deux ensembles sont dits disjoints s’ils n’admettent aucun élément commun. Par exemple, les ensembles \(\{10, 20, 30\}\) et \(\{4, 5, 6, 7\}\) sont disjoints.
La méthode isdisjoint
Pour tester en Python le caractère disjoint de deux ensembles A et B, on utilise la méthode isdisjoint
:
| A = {10, 20, 30}
B = {4, 5, 6, 7}
A.isdisjoint(B)
|
Alternative avec l’opérateur d’intersection
Il serait possible aussi d’utiliser l’opérateur d’intersection d’ensembles et de tester s’il renvoie l’ensemble vide :
1
2
3
4
5
6
7
8
9
10
11
12 | A = {10, 20, 30}
B = {4, 5, 6, 7}
print(A)
print(B)
inter = A & B
sontDisjoints = True
if len(inter) != 0:
sontDisjoints = False
print(sontDisjoints)
|
| {10, 20, 30}
{4, 5, 6, 7}
True
|
- Ligne 6 :
inter
est l’ensemble vide.
- Lignes 9-10 : que A et B soient disjoints signifie que
inter
est l’ensemble vide et donc len(inter)
vaut 0.
- Ligne 9 : on aurait pu abréger la ligne en
if inter:
Réunion et intersection
L’intersection
L’intersection de deux ensembles s
et t
est l’ensemble formé des éléments appartenant aux deux ensembles s
et t
. Par exemple, l’intersection des ensembles \(s = \{1, 2, 3, 4\}\) et \(t= \{1, 2, 5, 6\}\) est l’ensemble \(\{1,2\}\).
La réunion
La réunion de deux ensembles s
et t
est l’ensemble formé des éléments appartenant à l’un des deux ensembles s
ou t
. Par exemple, la réunion des ensembles \(s = \{1, 2, 3, 4\}\) et \(t= \{1, 2, 5, 6\}\) est l’ensemble \(\{1, 2, 3, 4, 5, 6\}\).
Réunion et intersection en Python
Étant donné deux ensembles, pour chaque opération d’intersection ou de réunion, il existe de 4 procédés pour exécuter l’opération :
- soit en utilisant un opérateur
- soit en utilisant une méthode non mutatrice
- soit en utilisant une méthode mutatrice
- soit en utilisant une affectation augmentée
Le tableau ci-dessous résume les différentes possibilités :
|
Intersection |
Union |
Remarques |
Notation
mathématique |
\(A\cap B\) |
\(A\cup B\) |
|
Éléments
appartenant … |
… à \(A\) ET à \(B\) |
… à \(A\) OU à \(B\) |
|
Opérateur
Python |
A & B |
A | B |
Un nouvel
ensemble
est créé |
Méthode non
mutatrice |
A.intersection(B)
B.intersection(A) |
A.union(B)
B.union(A) |
Renvoie
l’ensemble
cherché sans
modifier
ni A ni B |
Méthode
mutatrice |
A.intersection_
update(B)
B.intersection_
update(A) |
A.update(B)
B.update(A) |
Modifie
l’ensemble
en attribut |
Affectation
augmentée |
A &= B
B &= A |
A |= B
B |= A |
Modifie
l’ensemble
référencé
à gauche |
Chaque catégorie est illustrée ci-dessous par des exemples.
Opérateurs d’intersection et de réunion
| s = {1, 2, 3, 4}
t= {1, 2, 5, 6}
print(s)
print(t)
print()
print("intersection ->", s & t)
print("union ->", s | t)
|
| {1, 2, 3, 4}
{1, 2, 5, 6}
intersection -> {1, 2}
union -> {1, 2, 3, 4, 5, 6}
|
En Python, l’intersection de deux ensembles s
et t
est s & t
. Le choix de l’opérateur &
(qui désigne une abréviation de et) rappelle que les éléments de l’intersection de s
et de t
sont les éléments appartenant à s
et à t
. Il est possible de prendre l’intersection r & s & t
de trois ensembles (ou de plus de trois ensembles).
En Python, la réunion de deux ensembles s
et t
est s | t
. Le choix de l’opérateur |
(qui, en programmation, désigne souvent un ou logique ou bit à bit) rappelle que les éléments de l’intersection de s
et de t
sont les éléments appartenant à s
ou à t
. Il est possible de prendre la réunion r | s | t
de trois ensembles (ou de plus de trois ensembles).
Méthodes non mutatrices intersection
et union
| s = {1, 2, 3, 4}
t= {1, 2, 5, 6}
print(s)
print(t)
print()
print("intersection ->", s.intersection(t))
print("union ->", t.union(s))
print(s)
print(t)
|
| {1, 2, 3, 4}
{1, 2, 5, 6}
intersection -> {1, 2}
union -> {1, 2, 3, 4, 5, 6}
{1, 2, 3, 4}
{1, 2, 5, 6}
|
L’intersection de deux ensembles s
et t
est s.intersection(t)
ou encore t.intersection(s)
. De même, s.union(t)
est la réunion de s
et de t
.
La méthode intersection
appliquée à s
ne modifie pas s
(comparer lignes 16 et11). La méthode intersection
renvoie l’intersection des deux ensembles.
C’est analogue pour la méthode union
.
Méthodes mutatrices intersection_update
et update
1
2
3
4
5
6
7
8
9
10
11
12 | s = {1, 2, 3, 4}
t= {1, 2, 5, 6}
print(s)
print(t)
print()
s.intersection_update(t)
print("intersection ->", s)
print("----------------------------")
s = {1, 2, 3, 4}
s.update(t)
print("union ->", s)
|
| {1, 2, 3, 4}
{1, 2, 5, 6}
intersection -> {1, 2}
----------------------------
union -> {1, 2, 3, 4, 5, 6}
|
La méthode intersection
appliquée à s
modifie le contenu de s
(comparer lignes 13 et 16). La méthode intersection
(ligne 7) ne renvoie rien (ou plutôt None
).
C’est analogue pour la méthode union
.
Affectation augmentée pour l’intersection et la réunion
L’ensemble qui est à gauche de l’affectation augmentée est modifié :
| s = {1, 2, 3, 4}
t= {1, 2, 5, 6}
print(s)
print(t)
print()
s &= t
print("intersection ->",s)
s |= t
print("union ->", s)
|
| {1, 2, 3, 4}
{1, 2, 5, 6}
intersection -> {1, 2}
union -> {1, 2, 5, 6}
|
Différences d’ensembles
Mathématiquement, il existe deux types d’opérations de différences entre deux ensembles \(A\) et \(B\) :
- la différence simple \(A-B\) encore notée \(A\setminus B\) en mathématiques
- la différence symétrique notée \(A\Delta B\) en mathématiques.
Étant donné deux ensembles, pour chacune des deux opérations de différence, il existe 3 procédés pour exécuter l’opération :
- soit en utilisant un opérateur
- soit en utilisant une méthode modifiant l’un des ensembles
- soit en utilisant une affectation augmentée modifiant l’un des ensembles
Le tableau ci-dessous résume les différentes possibilités :
|
Différence
simple |
Différence
symétrique |
Opération
mathématique |
\(A-B\) ou
\(A\setminus B\) |
\(A\Delta B\) |
Éléments
appartenant |
à \(A\)
mais pas à \(B\) |
soit à \(A\)
soit à \(B\) |
Exemple
\(A=\{1,2,5\}\) et
\(B=\{1,2,3,4\}\) |
\(\{5\}\) |
\(\{5,3,4\}\) |
Opérateur
Python |
A - B |
A ^ B |
Méthode
de set |
A.difference(B) |
A.symmetric_diff
erence(B) |
Opérateur
augmenté |
A -= B |
A ^= B |
L’opérateur ^
est parfois appelé XOR
pour exclusive or qui correspond à soit … soit … c’est-à-dire un ou exclusif.
Opérateurs de différence : exemple
| A = {1, 2, 5}
B = {1, 2, 3, 4}
print(A)
print(B)
print()
print("A - B ->", A - B)
print("A ^ B ->", A ^ B)
|
| {1, 2, 5}
{1, 2, 3, 4}
A - B -> {5}
A ^ B -> {3, 4, 5}
|
Méthode pour la différence : exemple
| A = {1, 2, 5}
B = {1, 2, 3, 4}
print(A)
print(B)
print()
print("A.difference(B) ->", A.difference(B))
print("A.symmetric_difference(B) ->", A.symmetric_difference(B))
print()
print(A)
print(B)
|
| {1, 2, 5}
{1, 2, 3, 4}
A.difference(B) -> {5}
A.symmetric_difference(B) -> {3, 4, 5}
{1, 2, 5}
{1, 2, 3, 4}
|
Ces méthodes créent de nouveaux ensembles et ne modifient pas les ensembles sur lesquels elles agissent.
Affectation augmentée : exemple
L’ensemble qui est à gauche de l’affectation augmenté est modifié :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | A = {1, 2, 5}
B = {1, 2, 3, 4}
print(A)
print(B)
print()
A -= B
print("A - B ->", A)
print("---------------------")
A = {1, 2, 5}
B = {1, 2, 3, 4}
print(A)
print(B)
print()
A ^= B
print("A ^ B ->", A)
|
16
17
18
19
20
21
22
23
24 | {1, 2, 5}
{1, 2, 3, 4}
A - B -> {5}
---------------------
{1, 2, 5}
{1, 2, 3, 4}
A ^ B -> {3, 4, 5}
|
Comparaison des différentes opérations sur des ensembles set
Pour chacune des opérations mathématiques suivantes
- l’intersection,
- la réunion,
- la différence
- la différence symétrique
Python propose deux façons de la réaliser avec des ensembles de type set
. Comme le principe est le même pour chaque opération, seul le cas de la réunion sera présenté.
Création d’un nouvel ensemble
Soient s
et t
des ensembles. Alors s | t
est un nouvel ensemble qui contient des références vers les éléments de la réunion. Il en est de même de l’ensemble s.union(t)
.
L’intérêt est que les références vers les objets de s
et de t
sont préservées. La contrepartie est que des références vers des objets de s
et de t
sont recopiées :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | s = {1, 2, 3, 4}
t= {1, 2, 5, 6}
print("s :", s)
print("t :", t)
print()
print("id(s)->", id(s))
print("id(t)->", id(t))
print()
u = s | t
print("réunion :", u)
print()
print("id(s | t) :", id(u))
print()
print("id(s)->", id(s))
print("id(t)->", id(t))
print()
print("s :", s)
print("t :", t)
|
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | s : {1, 2, 3, 4}
t : {1, 2, 5, 6}
id(s)-> 3072177852
id(t)-> 3071850172
réunion : {1, 2, 3, 4, 5, 6}
id(s | t) : 3071851516
id(s)-> 3072177852
id(t)-> 3071850172
s : {1, 2, 3, 4}
t : {1, 2, 5, 6}
|
- Lignes 8 et 9 : les identités de
s
et t
avant l’opération de réunion.
- Lignes 11-15 : un nouvel objet est créé par le renvoi de
s | t
- Lignes 15 et 16 : les identités de
s
et t
après l’opération de réunion : elles sont inchangées, cf. lignes 26 et 27.
- Lignes 36 et 37 : les contenus de
s
et t
après l’opération de réunion : ils sont inchangés, cf. lignes 23 et 24.
La situation est essentiellement la même pour construire la réunion de s
et de t
en utilisant la méthode s.union
:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | s = {1, 2, 3, 4}
t= {1, 2, 5, 6}
print("s :", s)
print("t :", t)
print()
print("id(s)->", id(s))
print("id(t)->", id(t))
print()
u=s.union(t)
print("réunion :", u)
print()
print("id(s.union(t)) :", id(u))
print()
print("id(s)->", id(s))
print("id(t)->", id(t))
print()
print("s :", s)
print("t :", t)
|
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | s : {1, 2, 3, 4}
t : {1, 2, 5, 6}
id(s)-> 3072751292
id(t)-> 3072423612
réunion : {1, 2, 3, 4, 5, 6}
id(s.union(t)) : 3072424956
id(s)-> 3072751292
id(t)-> 3072423612
s : {1, 2, 3, 4}
t : {1, 2, 5, 6}
|
- On notera que la réunion de
s
et de t
est obtenue par une méthode appliquée à s
sans que s
soit modifié : s
référence le même objet et le contenu de cet objet est inchangé
Altération d’un des ensembles initiaux
Soient s
et t
des ensembles. Alors les instructions :
sont totalement équivalentes du point de vue de la création ou préservation d’objets. Elles conservent l’objet s
mais en modifient le contenu. Le bilan est le suivant :
- l’avantage est qu’il y a moins d’ajout de références que si un nouvel objet était complètement recréé.
- l’inconvénient est que le contenu initial de
s
est perdu. L’objet t
, lui, n’est en rien modifié.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | s = {1, 2, 3, 4}
t= {1, 2, 5, 6}
print("s :", s)
print("t :", t)
print()
print("id(s)->", id(s))
print("id(t)->", id(t))
print()
s.update(t)
print("réunion :", s)
print("id(s)->", id(s))
print("id(t)->", id(t))
print()
print("s :", s)
print("t :", t)
|
21
22
23
24
25
26
27
28
29
30
31
32 | s : {1, 2, 3, 4}
t : {1, 2, 5, 6}
id(s)-> 3072874172
id(t)-> 3072550588
réunion : {1, 2, 3, 4, 5, 6}
id(s)-> 3072874172
id(t)-> 3072550588
s : {1, 2, 3, 4, 5, 6}
t : {1, 2, 5, 6}
|
- Ligne 8 et 9 : les identités de
s
et t
avant l’opération de réunion.
- Ligne 11 : la construction de la réunion de
s
et t
: aucun nouvel ensemble n’est créé.
- Lignes 28 et 29 : les identités de
s
et t
après l’opération de réunion : elles sont inchangées, cf. lignes 24 et 25.
- Lignes 36 et 37 : le contenu de
s
a changé : désormais, s
représente la réunion des ensembles initiaux. Le premier contenu de s
est perdu. Le contenu de t
, lui, est inchangé.
Conversion implicite lors de l’appel de certaines méthodes
Si s
et t
sont des ensembles, s.union(t)
renvoie la réunion des deux ensembles. En réalité, une expression s.union(t)
ne suppose pas que t
soit de type ensemble mais, en fait, que t
soit n’importe quel conteneur susceptible d’être converti en un objet de type set
:
| s = set("ROSES")
t= "ORANGES"
print(s.union(t))
|
| {'E', 'R', 'S', 'A', 'N', 'O', 'G'}
|
La conversion s’applique aux opérations mathématiques et aux méthodes de set
données dans le tableau suivant :
opération |
méthode
non mutatrice |
méthode
mutatrice |
intersection |
intersection |
intersection_update |
réunion |
union |
update |
différence |
difference |
difference_update |
différence
symétrique |
symmetric_difference |
symmetric_difference_update |
Divers
Création, réunion d’ensembles par décompactage
L’exemple qui suit va permettre de mieux comprendre la possibilité de création d’ensemble par décompactage de certains itérables déjà créés :
| s1 = {10, 12, 14}
s2 = {11, 13, 15}
L = [23, 24, 25]
s= {20, *s1, *range(16, 20), 22, *L, 21, *s2}
print(s)
|
| {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
|
Depuis la version 3.5 de Python, il est possible de construire un ensemble en plaçant entre accolades et séparés par des virgules des éléments de cet ensemble ainsi que des références à des itérables à décompacter avec la syntaxe *
. Dans l’exemple ci-dessus, ligne 5, on construit un ensemble s
dont les éléments sont
- les entiers 20, 22 et 21
- les éléments de l’ensemble
s1
- les éléments de l’itérable
range(16, 20)
, donc les entiers de 16 à 19
- les éléments de la liste
L
- les éléments de l’ensemble
s2
La syntaxe *it
appliquée à un itérable telle qu’une liste, un ensemble, etc. à pour effet de placer dans l’ensemble les éléments de l’itérable. C’est juste du sucre syntaxique.
Un cas particulier de ce qui précède est l’obtention de la réunion de deux ensembles s1
et s2
par s = {*s1, *s2}
.
Faux éléments différents dans un ensemble
Un ensemble est formé d’éléments qui n’ont jamais la même valeur c’est-à-dire que si x
et y
sont deux éléments distincts de la liste des éléments d’un ensemble s
alors on a x !== y
. Par conséquent, si on définit l’ensemble
| s = {1, 42, True, 0, 1.0, False}
|
alors, cet ensemble ne contient pas six éléments mais en fait uniquement trois, à savoir 42, 1 et 0.
En effet, en Python, on a ceci :
| >>> 1 == True == 1.0
True
>>>
|
Ces trois éléments, bien qu’ayant des types différents, ont même valeur. De même, 0
et False
ont même valeur.
Copie d’ensemble
Pour copier un ensemble, on utilise le constructeur set
:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | A = {1, 2, 5}
B=set(A)
print("A =", A)
print("B =", B)
print("-"*10)
A.remove(1)
print("A =", A)
print("B =", B)
print("-"*10)
B.remove(2)
print("A =", A)
print("B =", B)
print("-"*10)
|
17
18
19
20
21
22
23
24
25 | A = {1, 2, 5}
B = {1, 2, 5}
----------
A = {2, 5}
B = {1, 2, 5}
----------
A = {2, 5}
B = {1, 5}
----------
|
Vider un ensemble de ses éléments
Au cours d’opérations avec un ensemble s
, on peut avoir besoin de supprimer tous les éléments de s tout en gardant une référence à s
(plutôt que de créer un nouvel ensemble). Pour cela, on utilise la méthode clear
:
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
s.clear()
print(s)
|
- Lignes 3 et 6 : après avoir appelé la méthode
clear
, s
référence l’ensemble vide.
Itérateur sur un ensemble
Si s
est un ensemble, on obtient un itérateur sur s
en utilisant la fonction standard iter
:
| s = {65, 31, 12, 81, 81, 65, 81, 12}
it = iter(s)
print(list(it))
|
iter(d)
itère sur les éléments de l’ensemble dans le même ordre, que lorsqu’on parcourt s
avec une boucle for
:
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(list(s))
it = iter(s)
for i in range(len(s)):
print(next(it))
|
| [[81, 65, 12, 31]
81
65
12
31
|
Accès à un élément arbitraire d’un ensemble
Si un ensemble n’est pas vide, comment accéder à un élément arbitraire de cet ensemble ? Pour y parvenir de façon économique et simple, il suffit de créer un itérateur sur l’ensemble et d’itérer juste une seule fois :
| s = {65, 31, 12, 81, 81, 65, 81, 12}
if s:
it = iter(s)
print(next(it))
|
La méthode pop
La méthode pop a un effet analogue en apparence puisqu’elle permet d’accéder à un élément arbitraire d’un ensemble ; toutefois la méthode pop
retire l’élément de l’ensemble (ce qui parfois n’est pas souhaité) :
| s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
print(s.pop())
print(s)
|
| {81, 31, 12, 65}
81
{31, 12, 65}
|
Parcourir en modifiant un ensemble
Il n’est pas possible de modifier un ensemble alors que l’ensemble est parcouru par une boucle for
:
| S = {2020}
for z in S:
S.add(42)
|
| Traceback (most recent call last):
File "_.py", line 2, in <module>
for z in S:
RuntimeError: Set changed size during iteration
|
Implémentation des ensembles
Les ensembles que Python utilise permettent d’accéder à un de ses éléments en un temps de O(1)
, autrement dit instantanément.
Les ensembles de l’implémentation CPython sont en fait des tables de hachage à adressage ouvert, et utilisent un algorithme de Knuth du tome 3 de AOCP, cf. le code source en C.
\(\mathtt{frozenset}\)
Les ensembles de type frozenset
Les ensembles de type frozenset
représentent une version immutable des ensembles de type set
. À la différence de set
, il n’existe pas d’ensembles littéraux de type frozenset
. Donc, pour créer un ensemble de type frozenset
, il faut impérativement utiliser le constructeur frozenset
, qui est analogue au constructeur set
:
| L = [65, 31, 12, 81, 81, 65, 81, 12]
s = frozenset(L)
print(s)
print(len(s))
|
| frozenset({65, 12, 81, 31})
4
|
Les ensembles de type frozenset
ont un comportement analogue aux ensembles de type set
.
Les opérateurs et les méthodes d’union, intersection, différence et différence symétrique sont inchangés. Par exemple :
| A = frozenset({1, 2, 5})
B = frozenset({1, 2, 3, 4})
print(A - B)
print(A.difference(B))
A -= B
print(A)
|
| frozenset({5})
frozenset({5})
frozenset({5})
|
Naturellement, comme les instances de frozenset
sont immutables, aucune méthode mutatrice de la classe set
ne s’applique à la classe frozenset
:
| a = frozenset({1, 2, 5})
a.remove(1)
|
| Traceback (most recent call last):
File "_.py", line 2, in <module>
a.remove(1)
AttributeError: 'frozenset' object has no attribute 'remove'
|
Un ensemble de type frozenset
est hachable et peut donc être élément d’un ensemble de type set
ou frozenset
(alors qu’un élément de type set ne peut être membre d’aucun ensemble) :
| a = frozenset([4, 6])
b = frozenset([5, 8])
c = frozenset([1, 3])
s = set([a, b, c])
print(s)
|
| {frozenset({1, 3}), frozenset({8, 5}), frozenset({4, 6})}
|
Comparaison des différentes opérations sur des frozenset
Comme pour les ensembles de types set
, si s
et t
sont des frozenset, les instructions s | t
et s.union(t)
vont créer un nouvel objet de type frozenset correspondant à la réunion des deux ensembles.
Le comportement entre des ensembles de type frozenset et set va différer pour l’affectation augmentée.
Pour des objets de type set
, une opération augmentée telle que s &= t
modifie le contenu de s
pour qu’il corresponde à la réunion des deux ensembles mais elle ne modifie pas l’identité de objet s
:
| s = {1, 2, 3, 4}
t= {1, 2, 5, 6}
print(id(s))
s &= t
print(id(s))
|
Pour des objets de type frozenset qui sont immutables, c’est différent :
| s = frozenset({1, 2, 3, 4})
t= frozenset({1, 2, 5, 6})
print(id(s))
s &= t
print(id(s))
|
Après l’affectation augmentée s &= t
, le nom s
ne réfère plus vers le même objet, un nouvel objet a été complètement créé ; en particulier, l’objet initial s
est perdu s’il n’est plus référencé par ailleurs.
Opérations entre des ensembles mixtes set
et frozenset
Il est possible d’effectuer des opérations sur des ensembles de types différents, à la fois set
et frozenset
. Ces opérations renvoient alors un objet du type du premier opérande :
| s = frozenset({1, 2, 3, 4})
t= {1, 2, 5, 6}
print(s | t)
print(type(t | s))
|
| frozenset({1, 2, 3, 4, 5, 6})
<class 'set'>
|
Il en va de même des méthodes :
| s = frozenset({1, 2, 3, 4})
t= {1, 2, 5, 6}
print(s.union(t))
print(type(t.union(s)))
|
| frozenset({1, 2, 3, 4, 5, 6})
<class 'set'>
|
Ainsi que des affectations combinées :
| s = frozenset({1, 2, 3, 4})
t= {1, 2, 5, 6}
s |= t
print(type(s))
s = frozenset({1, 2, 3, 4})
t |= s
print(type(t))
|
| <class 'frozenset'>
<class 'set'>
|