Ensembles

Définition d’un ensemble. Opérations sur les ensembles. Accès, suppression et ajout d’éléments d’un ensemble. Fonctions permettant de manipuler les ensembles. Exemples.

2

Les ensembles en Python

Ce sont des ensembles non ordonnés de valeurs distinctes. Ces valeurs peuventêtre de différents types.

Les tests d’appartenance de même que les opérations d’union et d’intersectionfonctionnent comme attendu en Python.

Il est possible de tester l’appartenance à un ensemble à l’aide des opérateurs in etnot in, d’obtenir le cardinal d’un ensemble à l’aide de la fonction intégrée len() et deparcourir les éléments d’un ensemble à l’aide de boucles.

Puisque les ensembles ne sont pas ordonnés, il n’est pas possible d’utiliser unindice ni de sélectionner une tranche, et il n’existe pas de clé permettant d’accéderaux valeurs.

Il existe 2 types d’ensembles :

set : On peut ajouter ou supprimer des éléments à ce type d’ensemble; parconséquent, ils ne peuvent être utilisés comme clés de dictionnaire.

frozenset : On ne peut ajouter ou supprimer des éléments à ce typed’ensemble; par contre, ils peuvent être utilisés comme clésde dictionnaire ou comme membres d’un autre ensemble.

3

Symboles d’opérations et de relations s’appliquant aux ensembles

4

Comment créer des ensembles et leur affecter des valeurs ?

>>> S = set("Nous avons un ensemble de valeurs distinctes.")>>> print Sset(['a', ' ', 'c', 'b', 'e', 'd', 'i', 'm', 'l', 'o', 'N', '.', 's', 'r', 'u', 't', 'v', 'n'])>>> len(S)18>>> type(S)<type 'set'>>>> T = frozenset("Nous avons un ensemble de valeurs distinctes.")>>> print Tfrozenset(['a', ' ', 'c', 'b', 'e', 'd', 'i', 'm', 'l', 'o', 'N', '.', 's', 'r', 'u', 't', 'v', 'n'])>>> len(T)18>>> type(T)<type 'frozenset'>>>> S == TTrue

Il n’existe pas de syntaxe particulière pour les ensembles comme il en existe parexemple pour les listes et pour les dictionnaires.

La seule méthode de création possible consiste à utiliser les fonctions set() etfrozenset().

Comment créer des ensembles et leur affecter des valeurs ?

On peut créer un ensemble à l’aide d’une liste, d’un tuple ou d’un dictionnaire.

>>> Voyelles = set(["a", "e", "i", "o", "u", "y"])>>> print Voyellesset(['a', 'e', 'i', 'o', 'u', 'y'])

>>> Voyelles = set(("a", "e", "i", "o", "u", "y"))>>> print Voyellesset(['a', 'e', 'i', 'o', 'u', 'y'])

>>> Voyelles = set({0:"a", 1:"e", 2:"i", 3:"o", 4:"u", 5:"y"})>>> print Voyellesset([0, 1, 2, 3, 4, 5])>>> Voyelles = set({0:"a", 1:"e", 2:"i", 3:"o", 4:"u", 5:"y"}.items())>>> print Voyellesset([(0, 'a'), (2, 'i'), (1, 'e'), (5, 'y'), (4, 'u'), (3, 'o')])>>> Voyelles = set({0:"a", 1:"e", 2:"i", 3:"o", 4:"u", 5:"y"}.keys())>>> print Voyellesset([0, 1, 2, 3, 4, 5])

Si aucun argument n’est fourni, il y a création d’un ensemble vide.

>>> set()set([])>>> set([])set([])>>> set(())set([])

6

Comment accéder aux valeurs d’un ensemble ?

On a besoin de parcourir les éléments d’un ensemble ou de vérifier si un élémentfait partie ou non d’un ensemble.

>>> C = "Nous avons un ensemble de valeurs distinctes.">>> S = set(C)>>> for c in S:

print c, C.count(c)a 2 6c 1b 1e 6d 2i 2m 1l 2o 2N 1. 1s 6r 1u 3t 2v 2n 4

7

Comment modifier un ensemble ?

1ière façon : ajouter un élément à un ensemble (add)

>>> voyelles = set("aeiou")>>> voyelles.add("y")>>> print voyellesset(['a', 'e', 'i', 'o', 'u', 'y'])

2ième façon : ajouter des éléments à un ensemble (update)

>>> voyelles_et_chiffres = set("aeiouy")>>> voyelles_et_chiffres.update("0123456789")>>> print voyelles_et_chiffresset(['a', '9', 'e', 'i', 'o', '1', '0', '3', '2', 'u', '4', '7', '6', 'y', '5', '8'])>>> >>> voyelles_et_chiffres = set("aeiouy")>>> voyelles_et_chiffres.update(range(10))>>> print voyelles_et_chiffresset(['a', 0, 2, 3, 'e', 5, 6, 1, 'i', 9, 7, 'o', 8, 'u', 'y', 4])>>> >>> voyelles_et_chiffres = set("aeiouy")>>> voyelles_et_chiffres.update([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])>>> print voyelles_et_chiffresset(['a', 0, 2, 3, 'e', 5, 6, 1, 'i', 9, 7, 'o', 8, 'u', 'y', 4])

8

Comment modifier un ensemble ?3ième façon : enlever un élément faisant partie d’un ensemble (remove),

enlever un élément à un ensemble s’il en fait partie (discard),enlever et retourner un élément quelconque d’un ensemble (pop).

>>> chiffres = set(range(11))>>> print chiffresset([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])>>> chiffres.remove(10)>>> print chiffresset([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

4ième façon : enlever des éléments à un ensemble (-=)

>>> print chiffresset([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])>>> >>> >>> chiffres -= set([4, 6, 8, 9])>>> print chiffresset([0, 1, 2, 3, 5, 7])

Comment supprimer un ensemble ?

del chiffres ou attendre que l’ensemble ait quitté sa portée.

On peut aussi supprimer tous les éléments d’un ensemble avec la méthode clear().

9

Opérateurs sur les ensembles de même type ou de types différents

Appartenance (in, not in)

Sert à déterminer si un élément est ou n’est pas membre d’un ensemble.

>>> Prenoms = set(["Luc", "Louis", "Jean"])>>> "Luc" in PrenomsTrue

Égalité / inégalité d’ensembles

Sert à tester l’égalité entre ensembles, c’est-à-dire si chaque élément de chaqueensemble est aussi élément de l’autre ensemble. Les ensembles peuvent être demême type ou de types différents.

>>> s = set(range(5,10))>>> t = frozenset([5, 6, 7, 8, 9])>>> s == tTrue>>> set("soir") != set("rois")False

10

Sous-ensemble de ou sur-ensemble de (<, <=, >, >=)Inégalité stricte :

A < B signifie que A est un sous-ensemble de B mais n’est pas égal.A > B signifie que A est un sur-ensemble de B mais n’est pas égal.

Inégalité au sens large :A <= B signifie que A est un sous-ensemble de B mais les 2 ensembles

peuvent être égaux.A >= B signifie que A est un sur-ensemble de B mais les 2 ensembles

peuvent être égaux.

>>> groupeA = set(["Luc", "Pierre", "Jacques"])>>> groupeB = set(["Lise", "Pierre", "Jacques", "Jean", "Luc"])>>> groupeA < groupeBTrue

Union (|)

Cette opération est équivalente au OU logique entre ensembles. L’union de 2ensembles est un autre ensemble dont chaque élément appartient au moins àl’un des 2 ensembles. union() est une méthode équivalente à cette opération.

>>> s = set("aeiouy") | set(range(10))>>> print sset([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'e', 'i', 'o', 'u', 'y'])>>> set("aeiouy").union(set(range(10)))set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'e', 'i', 'o', 'u', 'y'])

11

Intersection (&)

Cette opération est équivalente au ET logique entre ensembles. L’intersectionde 2 ensembles est un autre ensemble dont chaque élément appartient aux 2ensembles de départ. intersection() est une méthode équivalente à cette opération.

>>> set(range(10)) & set(range(5, 15))set([8, 9, 5, 6, 7])>>> set("saperlipopette") & set("poulie")set(['i', 'p', 'e', 'l', 'o'])

Différence ou complément relatif (-)

La différence de 2 ensembles est unautre ensemble dont chaque élémentappartient au premier ensemble maispas au second. difference() est uneméthode équivalente à cette opération.

>>> set("proximités") - set("permissivité")set(['x', 'o'])

Différence symétrique (^)

Cette opération est équivalente à un OU exclusif entre ensembles. La différencesymétrique de 2 ensembles est un autre ensemble dont chaque élément appartientà l’un des ensembles mais pas à l’autre. symmetric_difference() est une méthodeéquivalente à cette opération.

>>> set("proximités") ^ set("permissivité")set(['e', 'o', 'v', 'x'])

12

Opérations sur des ensembles de types différents

Si les objets sont tous deux du type set ou frozenset, le résultat est de même typeque les opérandes; mais si l’on effectue l’opération sur des ensembles de typesdifférents, le type de l’ensemble résultant est le même que celui de l’opérande degauche.

>>> set("proximités") ^ frozenset("permissivité")set(['e', 'o', 'v', 'x'])>>> frozenset("proximités") ^ frozenset("permissivité")frozenset(['e', 'o', 'v', 'x'])>>> frozenset("proximités") ^ set("permissivité")frozenset(['e', 'o', 'v', 'x'])

Note : L’opérateur + n’est pas un opérateur admis avec des ensembles.

13

Opérateurs s’appliquant uniquement aux ensembles de type set seulement

|=

>>> s = set("proximités")>>> s |= set("permissivité")>>> print sset(['é', 'e', 'i', 'm', 'o', 'p', 's', 'r', 't', 'v', 'x'])

Cet opérateur ajoute un ou plusieurs membres d’un autre ensemble à l’ensembleexistant. update() est une méthode équivalente à cette opération.

&= >>> s = set("proximités")>>> s &= set("permissivité")>>> print sset(['p', 'é', 'm', 'i', 's', 'r', 't'])

Cet opérateur ne conserve que les membresde l’ensemble existant qui sont égalementmembres de l’autre ensemble.intersection_update() est une méthode équivalenteà cette opération.

-=

>>> s = set("proximités")>>> s -= set("permissivité")>>> print sset(['x', 'o'])

Cet opérateur ne conserve que les membres de l’ensemble existant qui ne sontpas membres de l’autre ensemble. difference_update() est une méthodeéquivalente à cette opération.

14

^=

>>> s = set("proximités")>>> s ^= set("permissivité")>>> print sset(['e', 'o', 'v', 'x'])

Cet opérateur ne conserve que les membres appartenant à l’un des deuxensembles d’origine mais pas aux deux. symmetric_difference_update() estune méthode équivalente à cette opération.

Fonctions intégrées

len() Retourne la cardinalité de l’ensemble.

>>> len(set("0123456789"))10>>> len(range(10))10>>> len(set(["a", "e", "i", "o", "u", "y"]))6

15

>>> sset(['e', 'o', 'v', 'x'])>>> t = s.copy()>>> print tset(['x', 'e', 'o', 'v'])>>> t.add("u")>>> print sset(['e', 'o', 'v', 'x'])>>> print tset(['x', 'e', 'u', 'o', 'v'])

Nous avons déjà mentionné l’existence de plusieurs méthodes s’appliquant auxensembles équivalentes à des opérateurs.

Il existe une méthode qui ne possède pas d’opérateur équivalent : copy();elle retourne un nouvel ensemble qui est une copie de l’ensemble existant.

16

# Déterminer tous les nombres premiers entre 2 et n.#n = input("Entrez la valeur de n : ")

Ensemble = set(range(2, n+1))Nombres_premiers = set()

V = 2while (Ensemble != set()): if (V in Ensemble): Nombres_premiers.add(V) W = V while (W <= n): if (W in Ensemble): Ensemble.remove(W) W = W + V V = V + 1print Nombres_premiers

Recherche des nombres premiers entre 2 et n.

17

Entrez la valeur de n : 1000set([2, 3, 5, 7, 521, 11, 13, 17, 19, 23, 29, 31, 547, 37, 41, 43, 557, 47, 563, 53, 569, 59, 769, 61,577, 67, 991, 71, 73, 587, 79, 593, 83, 599, 89, 607, 97, 101, 103, 617, 107, 109, 113, 787, 631,127, 641, 131, 601, 647, 137, 139, 653, 823, 659, 149, 151, 157, 709, 673, 163, 677, 167, 683,173, 541, 179, 181, 701, 191, 193, 197, 199, 859, 719, 211, 727, 733, 223, 227, 229, 743, 233,239, 241, 757, 761, 251, 257, 773, 263, 269, 271, 643, 277, 281, 283, 797, 293, 809, 811, 619,307, 821, 311, 313, 827, 317, 829, 839, 331, 337, 739, 853, 857, 347, 349, 863, 523, 353, 571,359, 691, 877, 367, 881, 883, 373, 887, 379, 383, 389, 907, 397, 911, 661, 401, 919, 409, 751,929, 419, 421, 937, 941, 431, 433, 947, 439, 953, 443, 449, 967, 457, 971, 461, 463, 977, 467,983, 479, 997, 487, 491, 613, 499, 503, 509])

Pour obtenir ces valeurs en ordre croissant, on procède comme suit :

Liste_Nombres_premiers = list(Nombres_premiers)print sorted(Liste_Nombres_premiers)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311,313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557,563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661,673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809,811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937,941, 947, 953, 967, 971, 977, 983, 991, 997]

18

>>> U = set([233, 67, 34, 89, 1234, 765, 450, 10, 77])>>> V = U.copy()>>> min = V.pop()>>> while (V != set()):

w = V.pop()if (w < min): min = w

>>> print min10

Recherche du minimum dans un ensemble.

19

Produit cartésien de deux ensembles quelconques.

# Étant donné 2 ensembles quelconques U et V, construire un nouvel ensemble# U x V qui correspond au produit cartésien de ces deux ensembles et afficher# dans l'ordre ce nouvel ensemble.

U = set([45, 23, 98, 2, 8, 55])V = set(["Pierre", "Paul", "Luc"])W = set()

S = U.copy()if (U != set() and V != set()): while (S != set()): i = S.pop() T = V.copy() while (T != set()): j = T.pop() W.add((i,j))

print sorted(list(W))

20

Algorithme de calcul du kième plus petit élément d’une suite

Étape 0. Créer une liste vide Suite.

Étape 1. Tant que l’élément saisi n’est pas le caractère ‘#’ajouter à la liste l’élément saisi.

Étape 2. Saisir la valeur entière k entre 1 et la longueur de la suite.

Étape 3. Conserver la valeur de k dans Valeur_de_k.

Étape 4. Tant et aussi longtemps que le k ième plus petit élément n’est pas trouvé

Étape 4.1 Créer 2 listes vides Gauche et Droite.Placer dans pivot la valeur de Suite[0].Initialiser à 0 la variable Nb_occurrences_du_pivot désignantle nombre d’occurrences du pivot choisi.

Étape 4.2 Pour chaque i ième élément de la suite Suitesi pivot > i ième élément, ajouter le i ième élément

à la liste Gauchesinon si pivot < i ième élément, ajouter le i ième élément

à la liste Droitesinon ajouter 1 à Nb_occurrences_du_pivot.

21

Étape 4.3 Si la longueur de la suite Gauche Valeur_de_kSuite = Gauche

sinonsi la longueur de la suite Gauche + Nb_occurrences_du_pivot >=

Valeur_de_k): pivot est l’élément cherché, c’est terminé.

sinonValeur_de_k -= ( longueur de la suite Gauche +

Nb_occurrences_du_pivot)Suite = Droite

Étape 5. Afficher la valeur du pivot qui correspond bien au k ième plus petit élémentde la suite.

22

Calcul du kième plus petit élément d’une suite

# Saisir les éléments d'une suite. Pour terminer, entrez le caractère #.

Suite = set()while True:

element = input("Entrez un élément de la suite : ")if (element == "#"): breakSuite.add(element)

print "La suite est : ", Suite

# Saisir la valeur entière k.

k = input("Entrez l'indice k : ")

# Déterminer le k ième plus petit élément de la suite et ranger sa valeur# dans une variable pivot.

# À compléter ……

# Affichage du k ième plus petit élément de la suite.

print "Le %5d ième plus petit élément de la suite est : %5d" % (k, pivot)

23

Calcul du kième plus petit élément d’une suite

# Déterminer le k ième plus petit élément de la suite et ranger sa valeur# dans la variable pivot.Valeur_de_k = kFin = Truewhile(Fin): Gauche = set() Droite = set() Nb_occurrences = 1 pivot = Suite.pop() while(len(Suite) != 0): element = Suite.pop() if (pivot > element): Gauche.add(element) elif (pivot < element): Droite.add(element) else: Nb_occurrences += 1 if(len(Gauche) >= Valeur_de_k): Suite = Gauche.copy() elif((len(Gauche) + Nb_occurrences) >= Valeur_de_k): Fin = False else: Valeur_de_k -= (len(Gauche) + Nb_occurrences) Suite = Droite.copy()