Les Ensembles (Sets) en Python

1. Introduction

1.1 Définition

Un ensemble (set) en Python est une structure de données non ordonnée et qui ne contient pas de doublons. Les ensembles sont utilisés pour représenter des collections d'éléments uniques, et ils offrent des opérations efficaces pour les tests d'appartenance et les opérations mathématiques sur les ensembles (union, intersection, différence, etc.).

1.2 Contextualisation

Comparaison avec d'autres structures de données Python :

  • Listes : Mutables, ordonnées, permettent les doublons, non hashables.
  • Tuples : Immuables, ordonnés, permettent les doublons, hashables.
  • Ensembles : Mutables, non ordonnés, pas de doublons
  • Dictionnaires : Mutables, ordonnés (depuis Python 3.7), paires clé-valeur uniques

1.3 Cas d'utilisation

Les ensembles sont particulièrement adaptés pour :

  • Éliminer les doublons d'une collection d'éléments.
  • Vérifier rapidement si un élément existe dans une collection (test d'appartenance).
  • Réaliser des opérations mathématiques sur les ensembles (union, intersection, différence, différence symétrique).
  • Représenter des groupes uniques d'éléments (par exemple, les permissions d'un utilisateur).
  • Implémenter des algorithmes qui requièrent l'unicité des valeurs, comme la détection de cycles dans un graphe ou le calcul des ensembles de couverture.

2. Caractéristiques Fondamentales

2.1 Non-ordonnancement

Les ensembles en Python sont des collections non ordonnées. L'ordre des éléments à l'intérieur d'un ensemble n'est pas garanti et peut varier. Cela signifie que vous ne pouvez pas accéder aux éléments d'un ensemble par leur position (index). 


# Demonstrating unordered nature of sets
my_set = {3, 1, 2}
print(f"Original set: {my_set}")

# Iteration order is not predictable
print("Iterating through the set:")
for element in my_set:
  print(element)

2.2 Unicité

Les ensembles ne contiennent pas de doublons. Si vous ajoutez plusieurs fois le même élément à un ensemble, il n'apparaîtra qu'une seule fois. L'ajout d'un élément déjà présent n'aura aucun effet. 

 
# Demonstrating uniqueness of elements
my_set = {1, 2, 2, 3, 3, 3}
print(f"Set with duplicates: {my_set}")

2.3 Mutabilité

Les ensembles sont mutables, ce qui signifie que vous pouvez ajouter ou supprimer des éléments après la création de l'ensemble. Cependant, les éléments d'un ensemble doivent être de types de données hashables (immuables), car les ensembles utilisent ces valeurs pour stocker et rechercher les éléments. Les ensembles eux-mêmes ne sont pas hashables et ne peuvent pas être éléments d'un autre ensemble. Les éléments hashables autorisés incluent les nombres, les chaînes de caractères et les tuples (qui ne contiennent que des éléments hashables). Les listes et les dictionnaires ne sont pas hashables. 

# Demonstrating mutability of sets
  my_set = {1, 2, 3}
  print(f"Original set: {my_set}")

  # Adding elements
  my_set.add(4)
  print(f"After adding 4: {my_set}")

  # Removing elements
  my_set.remove(2)  # Raises KeyError if element is not present
  # my_set.discard(2) # Does not raise an error if element is not present (safer)
  print(f"After removing 2: {my_set}")

  # Trying to add a non-hashable type (e.g., a list) will raise an error:
  # my_set.add([5, 6]) # TypeError: unhashable type: 'list'

3. Création et Constructeur

3.1 Syntaxe de création

En Python, les ensembles peuvent être créés de plusieurs manières :

  • Utilisation des accolades {} (notation littérale)
  • Utilisation du constructeur set()
  • Compréhensions d'ensemble (similaires aux compréhensions de liste) 

# Different ways to create sets

# Empty set (note: {} creates an empty dictionary, not an empty set)
empty_set1 = set()

# Set with initial values
numbers = {1, 2, 3, 4, 5}
mixed_types = {1, "hello", 3.14, (1,2)} #Tuple is hashable, so it can be set member

# Using the set() constructor with other iterables
from_list = set([1, 2, 3])
from_string = set("Python")
from_tuple = set((1, 2, 3))
from_range = set(range(5))

# Set comprehension
squares = {x**2 for x in range(1, 6)}

print(f"From list: {from_list}")
print(f"From string: {from_string}")
print(f"From tuple: {from_tuple}")
print(f"From range: {from_range}")
print(f"Squares: {squares}")

3.2 Conversion

Le constructeur set() permet de convertir d'autres types de données itérables en ensembles, en éliminant les doublons. Le constructeur tentera d'itérer sur l'objet fourni et d'ajouter chaque élément unique à l'ensemble. 


# Converting other data types to sets

# From list
list_data = [10, 20, 30, 10]
set_from_list = set(list_data)

# From string
string_data = "Hello"
set_from_string = set(string_data)

# From tuple
tuple_data = (1, 2, 3, 1)
set_from_tuple = set(tuple_data)

# From dictionary (gets the keys)
dict_data = {"a": 1, "b": 2, "c": 3}
set_from_dict_keys = set(dict_data)

print(f"From list: {set_from_list}")
print(f"From string: {set_from_string}")
print(f"From tuple: {set_from_tuple}")
print(f"From dict keys: {set_from_dict_keys}")

4. Opérations de Base

4.1 Ajout et suppression d'éléments

Les ensembles en Python offrent plusieurs méthodes pour ajouter et supprimer des éléments :

  • add() : Ajoute un élément à l'ensemble. Si l'élément existe déjà, l'ensemble n'est pas modifié.
  • remove() : Supprime un élément. Lève une erreur KeyError si l'élément n'existe pas. Il est donc important de vérifier l'existence de l'élément avant de l'utiliser dans un code robuste.
  • discard() : Supprime un élément si présent. Ne lève pas d'erreur si l'élément n'existe pas. C'est la méthode la plus sûre pour la suppression d'un élément si vous n'êtes pas certain de son existence.
  • pop() : Supprime et retourne un élément aléatoire de l'ensemble. Cette méthode est rarement utilisée car l'ordre des ensembles est non-déterminé. Lève une erreur KeyError si l'ensemble est vide.
  • clear() : Supprime tous les éléments de l'ensemble. L'ensemble devient vide ( set() ). 

# Basic set operations
my_set = {1, 2, 3, 4}

# Adding elements
my_set.add(5)  # Add a single element
print(f"After adding 5: {my_set}")

# Removing elements
my_set.remove(3)  # Remove by value. Raises KeyError if not found
print(f"After removing 3: {my_set}")

my_set.discard(6)  # Remove by value. No error if not found (safer)
print(f"After discarding 6: {my_set}")

popped_element = my_set.pop()  # Remove and return a random element
print(f"Popped element: {popped_element}, Set: {my_set}")

my_set.clear()  # Remove all elements
print(f"After clearing: {my_set}")

4.2 Opérations de test d'appartenance

Python permet de vérifier si un élément est présent dans un ensemble avec l'opérateur in. Cette opération est très rapide (complexité temporelle O(1) en moyenne), ce qui rend les ensembles très efficaces pour les tests d'appartenance. 


# Test d'appartenance
my_set = {1, 2, 3}

# Checking existence
is_present = 2 in my_set  # Returns True
is_absent = 4 in my_set  # Returns False

print(f"Is 2 present? {is_present}")
print(f"Is 4 present? {is_absent}")

4.3 Opérations mathématiques sur les ensembles

Les ensembles en Python offrent plusieurs opérations mathématiques, qui sont fondamentales en théorie des ensembles :

  • union() ou | : Retourne un nouvel ensemble contenant tous les éléments des deux ensembles. L'opérateur | est une forme abrégée pour l'opération union().
  • intersection() ou & : Retourne un nouvel ensemble contenant les éléments communs aux deux ensembles. L'opérateur & est une forme abrégée pour l'opération intersection().
  • difference() ou - : Retourne un nouvel ensemble contenant les éléments qui sont dans le premier ensemble mais pas dans le second. L'opérateur - est une forme abrégée. L'ordre compte : set1 - set2 est différent de set2 - set1.
  • symmetric_difference() ou ^ : Retourne un nouvel ensemble contenant les éléments qui sont dans l'un ou l'autre des ensembles, mais pas les deux (c'est-à-dire l'union moins l'intersection). L'opérateur ^ est une forme abrégée. 

# Set operations
set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}

# Union
union_set = set1.union(set2)  # or set1 | set2
print(f"Union: {union_set}")

# Intersection
intersection_set = set1.intersection(set2)  # or set1 & set2
print(f"Intersection: {intersection_set}")

# Difference
difference_set = set1.difference(set2)  # or set1 - set2
print(f"Difference (set1 - set2): {difference_set}")

difference_set2 = set2.difference(set1)
print(f"Difference (set2 - set1): {difference_set2}")

# Symmetric difference
symmetric_difference_set = set1.symmetric_difference(set2)  # or set1 ^ set2
print(f"Symmetric difference: {symmetric_difference_set}")

5. Compréhensions d'Ensemble

5.1 Syntaxe de base

Les compréhensions d'ensemble sont une syntaxe concise et puissante pour créer des ensembles en Python, similaire aux compréhensions de liste. Elles permettent de transformer, filtrer et générer des données en une seule expression, tout en garantissant l'unicité des éléments.

La syntaxe de base est : {expression for item in iterable}. L'expression est évaluée pour chaque élément de l'itérable et le résultat est ajouté à l'ensemble. Les doublons sont automatiquement éliminés. 


# Basic set comprehension examples

# Creating a set of squares
squares = {x**2 for x in range(1, 11)}
print(f"Squares: {squares}")

# Creating a set of even numbers from a list
numbers = [1, 2, 2, 3, 4, 4, 5, 6]
even_numbers = {x for x in numbers if x % 2 == 0}
print(f"Even numbers: {even_numbers}")

# Creating a set with string manipulation
words = ["apple", "banana", "apple", "orange"]
unique_letters = {letter for word in words for letter in word}
print(f"Unique letters: {unique_letters}")

5.2 Compréhensions avec conditions

Les compréhensions d'ensemble peuvent inclure des conditions pour filtrer les éléments :

La syntaxe est : {expression for item in iterable if condition}. Seuls les éléments qui satisfont la condition sont inclus dans l'ensemble résultant. 


# Set comprehensions with conditions

# Filtering with a condition
numbers = range(1, 21)
odd_numbers = {x for x in numbers if x % 2 != 0}
print(f"Odd numbers: {odd_numbers}")

# Using conditional expressions (not as common, as the result would need to be unique)
letters = "hello world"
vowels = {char if char in "aeiou" else "*" for char in letters}  #  Note that if a value can appear multiple times (e.g., "l" in letters) but the set ensures it exists only once.
print(f"Vowels and '*': {vowels}")

# Combining multiple conditions (example of getting unique multiples of 2 and 3)
divisible_by_2_and_3 = {x for x in range(1, 31) if x % 2 == 0 and x % 3 == 0}
print(f"Divisible by both 2 and 3: {divisible_by_2_and_3}")

6. Copie et Références

6.1 Références et assignation

En Python, les variables de set sont des références aux objets en mémoire. Lorsqu'un set est assigné à une nouvelle variable, les deux variables font référence au même objet. Cela signifie que les modifications apportées via une variable affectent l'autre. C'est le comportement par défaut lors d'une assignation simple. 


# References and assignment

# Creating a set
original = {1, 2, 3, 4, 5}

# Assigning to a new variable (creates a reference, not a copy)
reference = original

# Modifying through the reference
reference.add(6)

# Both variables show the change
print(f"Original: {original}")
print(f"Reference: {reference}")

# Checking if they reference the same object
print(f"Same object? {original is reference}")

6.2 Méthodes de copie

Pour créer une copie indépendante d'un ensemble, Python offre une méthode:

  • shallow copy : set.copy(). Cela crée un nouveau set, mais si le set contient d'autres objets mutables (comme des listes), ces objets ne seront pas copiés. Les modifications apportées à ces objets mutables dans l'un des sets seront visibles dans l'autre.

Si vous avez besoin d'une copie en profondeur (deep copy) qui copie également les objets internes mutables, vous devrez utiliser le module copy et sa fonction deepcopy(). 


# Different ways to copy sets

# Original set
original = {1, 2, 3, 4, 5}

# Shallow copy methods
copy_set = original.copy()

# Modifying the original
original.add(6)

print(f"Original: {original}")
print(f"Copied set: {copy_set}")

# Demonstrating that the copy is shallow
original_with_list = {1, 2, [3, 4]}
try:
copy_shallow_with_list = original_with_list.copy()  # Will raise an error because lists are not hashable
except:
print("Cannot copy a set with a list (non-hashable)")


import copy
original_with_list = {1, 2, [3, 4]}
copy_deep_with_list = copy.deepcopy(original_with_list) # OK
original_with_list.get(2).append(5)

7. Itération

7.1 Boucles et itération

Les ensembles Python sont itérables, ce qui permet de parcourir leurs éléments de différentes manières :

  • Boucle for classique
  • Compréhensions d'ensemble

# Iterating through sets
my_set = {"apple", "banana", "cherry"}

# Basic for loop
print("Basic for loop:")
for fruit in my_set:
print(f"- {fruit}")

# Note: the order of iteration is not guaranteed.  It might appear random.

8. Performance

8.1 Complexité temporelle

La complexité temporelle des opérations sur les ensembles Python est importante à comprendre pour écrire du code efficace :

  • Test d'appartenance (in) : O(1) en moyenne, O(n) dans le pire des cas (collisions) - Très rapide. En moyenne, le temps d'accès est constant, grâce à l'utilisation de tables de hachage. Cependant, il est possible, dans des cas extrêmes (peu probables dans une implémentation bien conçue), que des collisions augmentent le temps d'accès.
  • Ajout (add) : O(1) en moyenne, O(n) dans le pire des cas (redimensionnement) - Rapide. L'ajout est généralement rapide, mais si la table de hachage doit être redimensionnée pour accueillir l'élément, cela peut prendre O(n) temps.
  • Suppression (remove, discard) : O(1) en moyenne, O(n) dans le pire des cas (redimensionnement) - Rapide. Similaire à l'ajout, la suppression est rapide en moyenne, mais peut prendre O(n) si un redimensionnement est nécessaire.
  • Union (|) : O(len(set1) + len(set2)). Il faut itérer sur les deux ensembles pour créer le nouvel ensemble résultant.
  • Intersection (&) : O(min(len(set1), len(set2))). Idem pour union(). Une optimisation vise à itérer sur le plus petit des deux ensembles pour chercher les éléments communs.
  • Différence (-) : O(len(set1)). Il faut itérer sur le premier ensemble pour déterminer quels éléments ne sont pas présents dans le second.

En résumé, les opérations de base sur les ensembles ont généralement une complexité temporelle constante (O(1)) ou linéaire (O(n)). La complexité temporelle de ces opérations rend les ensembles très performants pour de nombreuses tâches, notamment les tests d'appartenance et les opérations ensemblistes. 


# Performance demonstration
import time

# Create a large set
large_set = set(range(100000))

# Function to measure execution time
def measure_time(func, *args):
start = time.time()
result = func(*args)
end = time.time()
return (end - start) * 1000  # Convert to milliseconds

# Measure membership test time (O(1) on average)
membership_time = measure_time(lambda s: 99999 in s, large_set)
print(f"Membership test time: {membership_time:.4f} ms")

# Measure add time (O(1) on average)
add_time = measure_time(lambda s: s.add(100000), large_set.copy())
print(f"Add time: {add_time:.4f} ms")

# Measure intersection time
large_set2 = set(range(90000, 110000))
intersection_time = measure_time(lambda s1, s2: s1.intersection(s2), large_set, large_set2)
print(f"Intersection time: {intersection_time:.4f} ms")

9. Cas d'Utilisation Pratiques

9.1 Élimination des doublons

L'une des utilisations les plus courantes des ensembles est d'éliminer rapidement les doublons d'une liste ou d'une autre collection. C'est une opération très simple et efficace. 


# Removing duplicates from a list
my_list = [1, 2, 2, 3, 4, 4, 4, 5]
unique_list = list(set(my_list))  # Convert back to list if order is important.

print(f"Original list: {my_list}")
print(f"List with duplicates removed: {unique_list}")

9.2 Test d'appartenance

Les ensembles offrent un test d'appartenance très efficace. Ils sont plus rapides que les listes pour vérifier si un élément est présent. Il est fortement recommandé d'utiliser les ensembles si les performances sont critiques et si l'ordre des éléments n'est pas important. 


# Checking for existence
my_set = {1, 2, 3, 4, 5}

if 3 in my_set:
print("3 is in the set")

if 6 not in my_set:
print("6 is not in the set")

9.3 Opérations sur les ensembles (ex: permissions)

Les ensembles sont utiles pour représenter et manipuler des ensembles d'éléments, comme les permissions ou les rôles d'utilisateurs. Les opérations ensemblistes facilitent la gestion des droits et des accès. 


# Set operations for permissions or roles
admin_permissions = {"read", "write", "delete", "update"}
editor_permissions = {"read", "write", "update"}
viewer_permissions = {"read"}

# Checking if a user has specific permissions
def has_permission(user_permissions, required_permissions):
return required_permissions.issubset(user_permissions)

if has_permission(admin_permissions, {"read", "delete"}):
print("Admin has read and delete permissions")

# Finding the common permissions between admin and editor
common_permissions = admin_permissions.intersection(editor_permissions)
print(f"Common permissions: {common_permissions}")

# Finding permissions unique to the admin
admin_unique_permissions = admin_permissions.difference(editor_permissions)
print(f"Admin's unique permissions: {admin_unique_permissions}")

10. Exercices

10.1 Exercice 1: Manipulation de base

Créez un set avec les nombres 1 à 5, puis effectuez les opérations suivantes :

  • Ajoutez le nombre 6 au set.
  • Supprimez le nombre 3 du set.
  • Vérifiez si le nombre 2 est dans le set.
  • Créez un autre set avec les nombres 4, 5, 6, et 7. Effectuez les opérations d'union, d'intersection et de différence entre les deux sets. 

# Exercice 1: Solution

# Créer un set de nombres de 1 à 5
numbers = {1, 2, 3, 4, 5}
print(f"Set initial: {numbers}")

# 1. Ajouter 6
numbers.add(6)
print(f"Après ajout de 6: {numbers}")

# 2. Supprimer 3
numbers.discard(3) # utilise discard pour ne pas lever d'erreur si l'element n'existe pas
print(f"Après suppression de 3: {numbers}")

# 3. Vérifier si 2 est dans le set
if 2 in numbers:
print("Le nombre 2 est dans le set.")
else:
print("Le nombre 2 n'est pas dans le set.")

# 4. Opérations avec un autre set
other_numbers = {4, 5, 6, 7}

# Union
union_set = numbers | other_numbers # ou numbers.union(other_numbers)
print(f"Union: {union_set}")

# Intersection
intersection_set = numbers & other_numbers # ou numbers.intersection(other_numbers)
print(f"Intersection: {intersection_set}")

# Différence (numbers - other_numbers)
difference_set = numbers - other_numbers # ou numbers.difference(other_numbers)
print(f"Différence (numbers - other_numbers): {difference_set}")

10.2 Exercice 2: Applications des Sets

Considérez une situation de gestion de présence. On a deux listes, une pour les employés présents et une autre pour les employés qui étaient prévus. Utilisez les sets pour :

  • Trouver les employés qui étaient présents mais n'étaient pas prévus (absences non autorisées)
  • Trouver les employés qui étaient prévus mais absents (absences autorisées ou non)
  • Trouver tous les employés impliqués (présents ou prévus) 

# Exercice 2: Solution

# Employés présents et prévus
employes_presents = ["Alice", "Bob", "Charlie", "David"]
employes_prevus = ["Bob", "Charlie", "Eve", "Frank"]

# Convertir en sets
set_presents = set(employes_presents)
set_prevus = set(employes_prevus)

# 1. Absences non autorisées (présents non prévus)
absences_non_autorisees = set_presents - set_prevus
print(f"Absences non autorisées: {absences_non_autorisees}")

# 2. Absents (prévus mais non présents)
absents = set_prevus - set_presents
print(f"Absents: {absents}")

# 3. Tous les employés impliqués (union)
tous_employes = set_presents | set_prevus
print(f"Tous les employés impliqués: {tous_employes}")

10.3 Exercice 3: Analyse de données avec Sets

Vous avez deux fichiers contenant des listes de mots. Utilisez les sets pour :

  • Trouver les mots uniques qui apparaissent dans les deux fichiers.
  • Trouver tous les mots uniques apparaissant dans les deux fichiers.
  • Trouver les mots qui apparaissent dans le premier fichier mais pas dans le second. 

# Exercice 3: Solution

# Simuler le contenu des fichiers (remplacez ceci par la lecture de fichiers réels)
fichier1_mots = ["pomme", "banane", "orange", "pomme", "fraise"]
fichier2_mots = ["banane", "kiwi", "orange", "raisin"]

# Convertir en sets (pour se débarrasser des doublons)
set_fichier1 = set(fichier1_mots)
set_fichier2 = set(fichier2_mots)

# 1. Mots communs
mots_communs = set_fichier1 & set_fichier2
print(f"Mots communs: {mots_communs}")

# 2. Tous les mots uniques
tous_les_mots = set_fichier1 | set_fichier2
print(f"Tous les mots uniques: {tous_les_mots}")

# 3. Mots présents dans le fichier 1 mais pas dans le fichier 2
mots_fichier1_uniques = set_fichier1 - set_fichier2
print(f"Mots uniques dans le fichier 1: {mots_fichier1_uniques}")

11. Résumé et Comparaisons

Points clés à retenir sur sets Python :

  • Structure de données non ordonnée et mutable
  • Éléments uniques (pas de doublons).
  • Opérations mathématiques sur sets (union, intersection, différence, différence symétrique)
  • Utilisation efficace pour l'élimination des doublons
  • Accès rapide pour la vérification de l'appartenance (grâce au hachage)

Bonnes Pratiques

  • Utilisez les sets lorsque l'ordre des éléments n'est pas important et que l'unicité est requise.
  • Utilisez les sets pour des opérations de comparaison efficaces (intersection, union, etc.).
  • Préférez la syntaxe des opérateurs (|, &, -) pour plus de lisibilité.
  • Convertissez une liste en set ( set(ma_liste) ) pour éliminer rapidement les doublons.

12. Conclusion

Les sets sont des structures de données puissantes et efficaces en Python, particulièrement utiles pour gérer des collections d'éléments uniques et effectuer des opérations ensemblistes. Leur capacité à éliminer les doublons et à offrir un accès rapide en fait un outil précieux dans de nombreuses situations.

Points clés à retenir :

  • Les sets sont non ordonnés et contiennent uniquement des éléments uniques.
  • Ils offrent des opérations efficaces pour la comparaison et la manipulation de collections.
  • Ils sont utiles pour éliminer les doublons, vérifier l'appartenance et traiter des données ensemblistes.
  • Comprendre les sets vous aidera à écrire du code Python plus efficace et plus concis.

Maîtriser les sets et leurs opérations vous permettra de résoudre élégamment une grande variété de problèmes de programmation, notamment le traitement de données, la gestion de collections et l'optimisation des algorithmes. Les sets complètent les listes et les dictionnaires pour enrichir vos outils de développement Python.

That's all folks