Ensembles

\(\newcommand{\ds}{\displaystyle}\) \(\newcommand{\Frac}{\ds\frac}\) \(\renewcommand{\r}{\mathbb{ R}}\) \(\newcommand{\C}{\mathbb{ C}}\) \(\newcommand{\n}{\mathbb{ N}}\) \(\newcommand{\z}{\mathbb{ Z}}\) \(\newcommand{\Q}{\mathbb{ Q}}\) \(\newcommand{\N}{\mathbb{ N}}\) \(\newcommand{\n}{\mathbb{ N}}\) \(\newcommand{\ol}{\overline}\) \(\newcommand{\abs}[1]{\left| \,{#1} \right|}\) \(\newcommand{\pv}{\;;\;}\) \(\newcommand{\ens}[1]{\left\{ {#1} \right\}}\) \(\newcommand{\mens}[1]{\setminus\left\{ {#1} \right\}}\) \(\newcommand{\Par}[1]{\left({#1}\right)}\) \(\newcommand{\pe}[1]{\left\lfloor {#1} \right\rfloor}\) \(\newcommand{\trans}[1]{\,^t\!{#1}}\)

Ensembles

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 :

1
2
s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
3
{81, 31, 12, 65}
  • 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 :

1
2
s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
3
{81, 31, 12, 65}
  • 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 :

1
2
s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
3
{81, 31, 12, 65}
  • 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 :

1
2
3
4
s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
n = len(s)
print(n)
5
6
{81, 31, 12, 65}
4
  • 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 :

1
2
s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
3
{81, 31, 12, 65}

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 :

1
2
3
L = [65, 31, 12, 81, 81, 65, 81, 12]
s = set(L)
print(s)
4
{65, 12, 81, 31}
  • 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 :

1
2
3
s = set()
print(s)
print(len(s))
4
5
set()
0
  • 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é :

1
2
3
4
s = {65, 31, 12, 81, 81, 65, 81, 12}

print(42 in s)
print(42 not in s)
5
6
False
True

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 :

1
2
s = {42, "orange", "rose", 42, 2038}
print(s)
3
{'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 :

1
2
s = {[42, 81, 10], 100}
print(s)
3
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 :

1
2
s = {(42, 81, 10), 100}
print(s)
3
{100, (42, 81, 10)}
  • 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 :

1
2
3
4
a = set([4, 6])
b = set([5, 8])
c = set([1, 3])
s = set([a, b, c])
5
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 :

1
2
3
4
5
6
7
8
a = set([4, 2, 1])
print(a)

a.remove(1)
print(a)

a.add(100)
print(a)
 9
10
11
{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 :

1
2
3
s = {65, 31, 12, 81, 81, 65, 81, 12}
for x in s:
    print(x)
4
5
6
7
81
31
12
65

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

1
2
A={10 * i for i in range(1,11)}
print(A)
3
{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 :

1
2
A={10 * i for i in range(1,11) if i % 3 == 0}
print(A)
3
{90, 60, 30}

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 :

1
2
3
4
5
empty = set()
print(bool(empty))

non_empty = set([42, 2020])
print(bool(non_empty))
6
7
False
True

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 :

1
2
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 :

1
2
3
s = "BANANA"
S = set(s)
print(S)
4
{'A', 'N', 'B'}
  • 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 :

1
2
3
r = range(10)
S = set(r)
print(S)
4
{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 ») :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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)))
11
12
13
14
15
[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 :

1
2
3
4
5
s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
L = list(s)
print(L)
print(s)
6
7
8
{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 :

1
2
3
4
L = [65, 31, 12, 81, 81, 65, 81, 12]
print(L)
M = list(set(L))
print(M)
5
6
[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 :

1
2
3
4
5
6
7
8
9
s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)

z = s.add(42)
print(s)
print(z)

s.add(42)
print(s)
10
11
12
13
{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 :

1
2
3
4
5
6
7
8
s = {65, 31, 12, 81, 81, 65, 81, 12}

z = s.discard(81)
print(s)
print(z)

s.discard(81)
print(s)
 9
10
11
{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é :

1
2
3
4
5
s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
z = s.remove(81)
print(s)
print(z)
6
7
8
{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 :

1
2
3
s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
s.remove(42)
4
5
6
7
8
{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 :

1
2
3
4
5
s = {65, 31, 12, 81, 81, 65, 81, 12}
z = s.pop()

print(s)
print(z)
6
7
{31, 12, 65}
81
  • 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 :

1
2
3
4
s = {42}
s.pop()
s.pop()
print(s)
5
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 != :

1
2
3
4
5
6
s = {1, 2, 1, 3}
t = {2, 2, 1, 3, 3}
print(s)
print(t)
print(s == t)
print(s != t)
 7
 8
 9
10
{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

1
2
3
4
5
6
7
8
9
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)
10
11
12
13
14
15
{1, 2, 3}
{0, 1, 2, 3}
A <= B -> True
A < B -> True
A >= B -> False
A > B -> False

Illustration avec les méthodes

1
2
3
4
5
6
7
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))
 8
 9
10
11
{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 :

1
2
3
A = {10, 20, 30}
B = {4, 5, 6, 7}
A.isdisjoint(B)
4
True

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)
13
14
15
{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

1
2
3
4
5
6
7
8
s = {1, 2, 3, 4}
t= {1, 2, 5, 6}
print(s)
print(t)
print()

print("intersection ->", s & t)
print("union ->", s | t)
 9
10
11
12
13
{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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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)
11
12
13
14
15
16
17
{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)
13
14
15
16
17
18
{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é :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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)
11
12
13
14
15
{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

1
2
3
4
5
6
7
8
A = {1, 2, 5}
B = {1, 2, 3, 4}
print(A)
print(B)
print()

print("A - B ->", A - B)
print("A ^ B ->", A ^ B)
 9
10
11
12
13
{1, 2, 5}
{1, 2, 3, 4}

A - B -> {5}
A ^ B -> {3, 4, 5}

Méthode pour la différence : exemple

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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)
12
13
14
15
16
17
18
19
{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 :

  • s.update(t)
  • s |= t

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 :

1
2
3
s = set("ROSES")
t= "ORANGES"
print(s.union(t))
4
{'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 :

1
2
3
4
5
6
7
s1 = {10, 12, 14}
s2 = {11, 13, 15}
L = [23, 24, 25]

s= {20, *s1, *range(16, 20), 22, *L, 21, *s2}

print(s)
8
{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

1
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
2
3
>>> 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 :

1
2
3
4
s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
s.clear()
print(s)
5
6
{81, 31, 12, 65}
set()
  • 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 :

1
2
3
s = {65, 31, 12, 81, 81, 65, 81, 12}
it = iter(s)
print(list(it))
4
[81, 31, 12, 65]

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 :

1
2
3
4
5
6
s = {65, 31, 12, 81, 81, 65, 81, 12}
print(list(s))
it = iter(s)

for i in range(len(s)):
    print(next(it))
 7
 8
 9
10
11
[[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 :

1
2
3
4
5
s = {65, 31, 12, 81, 81, 65, 81, 12}

if s:
    it = iter(s)
    print(next(it))
6
81

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é) :

1
2
3
4
s = {65, 31, 12, 81, 81, 65, 81, 12}
print(s)
print(s.pop())
print(s)
5
6
7
{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 :

1
2
3
S = {2020}
for z in S:
    S.add(42)
4
5
6
7
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 :

1
2
3
4
L = [65, 31, 12, 81, 81, 65, 81, 12]
s = frozenset(L)
print(s)
print(len(s))
5
6
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 :

1
2
3
4
5
6
7
A = frozenset({1, 2, 5})
B = frozenset({1, 2, 3, 4})
print(A - B)
print(A.difference(B))

A -= B
print(A)
 8
 9
10
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 :

1
2
a = frozenset({1, 2, 5})
a.remove(1)
3
4
5
6
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) :

1
2
3
4
5
a = frozenset([4, 6])
b = frozenset([5, 8])
c = frozenset([1, 3])
s = set([a, b, c])
print(s)
6
{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 :

1
2
3
4
5
s = {1, 2, 3, 4}
t= {1, 2, 5, 6}
print(id(s))
s &= t
print(id(s))
6
7
3072579148
3072579148

Pour des objets de type frozenset qui sont immutables, c’est différent :

1
2
3
4
5
s = frozenset({1, 2, 3, 4})
t= frozenset({1, 2, 5, 6})
print(id(s))
s &= t
print(id(s))
6
7
3072052332
3072370252

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 :

1
2
3
4
s = frozenset({1, 2, 3, 4})
t= {1, 2, 5, 6}
print(s | t)
print(type(t | s))
5
6
frozenset({1, 2, 3, 4, 5, 6})
<class 'set'>

Il en va de même des méthodes :

1
2
3
4
5
s = frozenset({1, 2, 3, 4})
t= {1, 2, 5, 6}

print(s.union(t))
print(type(t.union(s)))
6
7
frozenset({1, 2, 3, 4, 5, 6})
<class 'set'>

Ainsi que des affectations combinées :

1
2
3
4
5
6
7
8
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))
 9
10
<class 'frozenset'>
<class 'set'>