Discussion :

[Narlen27]

Bonjour,
Es ce possible de créer des fonctions d'ensembles mathématiques(cardinalité, ajout, difference symétrique), mais sans utiliser la fonction set dans python?

Merci

[wiztricks]

Salut,

Cote "programmation" tout est possible. D'ailleurs les /set/ natifs de Python ne sont que "programmes".
Cela étant "comment" réaliser des fonctions équivalentes aux set natifs?
Ben ca commence par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
class Set(Collection):
      def union(...): pass
      def intersection(...): pass
      def is_empty(...): pass
...

reste a savoir par quoi remplacer Collection... Une liste? Un tuple? ...?
- W

[tyrtamos]

Bonjour,

Oui, et c'est assez simple. Dans les objets de base de Python, la liste peut porter n'importe quel objet (au sens de la POO), et donc peut représenter facilement un ensemble.

Petit exemple fait rapidement (à vérifier/optimiser) avec de simples nombres (Python 2.7):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
e1 = [1,2,3,4,5,6]
e2 = [4,5,7,8,9]
print "ensemble e1:", e1
print "ensemble e2:", e2
print
 
# cardinalité
print "cardinalité de e1:", len(e1)
print "cardinalité de e2:", len(e2)
print
 
# union
e = e1[:] # ne pas oublier le '[:]', sinon, e et e1 pointeraient sur la même donnée
for elem in e2:
    if elem not in e:
        e.append(elem)
print "union de e1 et e2:", e
print
 
# intersection
e = []
for elem in e1:
    if (elem in e2):
        e.append(elem)
print "intersection de e1 et e2:", e
print
 
# différence e1-e2
e = []
for elem in e1:
    if (elem in e1) and (elem not in e2):
        e.append(elem)
print "différence e1-e2:", e
print
 
# différence e2-e1
e = []
for elem in e2:
    if (elem in e2) and (elem not in e1):
        e.append(elem)
print "différence e2-e1:", e
print
 
# appartenance
elem = 2
print "appartenance de elem=2 dans e1:", elem in e1
print "appartenance de elem=2 dans e2:", elem in e2

Ce qui affiche:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ensemble e1: [1, 2, 3, 4, 5, 6]
ensemble e2: [4, 5, 7, 8, 9]
 
cardinalité de e1: 6
cardinalité de e2: 5
 
union de e1 et e2: [1, 2, 3, 4, 5, 6, 7, 8, 9]
 
intersection de e1 et e2: [4, 5]
 
différence e1-e2: [1, 2, 3, 6]
 
différence e2-e1: [7, 8, 9]
 
appartenance de elem=2 dans e1: True
appartenance de elem=2 dans e2: False

[wiztricks]

Oui, et c'est assez simple. Dans les objets de base de Python, la liste peut porter n'importe quel objet (au sens de la POO), et donc peut représenter facilement un ensemble.

Si c’était aussi simple, pourquoi la classe set de Python utilise un dict forçant les objets d'un set a être hashable?
- W

[tyrtamos]

Bonjour wiztricks,

La question portait sur la faisabilité, et j'ai prouvé qu'on pouvait y arriver avec des instructions basiques: ça donne bien les mêmes résultats que set, et ça répond aux définitions des ensembles.

Mais, je l'ai dit, c'était un code fait rapidement, et rien n'empêche de faire mieux, et en particulier plus vite. Dans la mesure où on évite les répétitions d'objets dans les ensembles, la solution avec dict parait évidente.

[Narlen27]

Bonjour Tyrtamos,

Merci, c'est super!.
Juste j'aimerais savoir comment supprimer les doublons dans la liste avant d'appliquer la fonction 'len' , dans le but d'avoir la cardinalité d'une liste avec des éléments uniques.

Je voulais aussi savoir comment créer des tests pour valider mes fonctions

Merci

[tyrtamos]

Bonjour,

Supprimer les doublons d'une liste peut se faire comme ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
e1 = [1, 2, 3, 4, 5, 6, 5, 6, 5, 5]
e = []
for elem in e1:
    if elem not in e:
       e.append(elem)
print e
[1, 2, 3, 4, 5, 6]

On peut aussi le faire en une seule ligne, mais je ne suis pas sûr que ce soit plus rapide:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
e = [elem for i, elem in enumerate(e1) if elem not in e1[:i]]
print e
[1, 2, 3, 4, 5, 6]

L'avantage de cette forme en une ligne est qu'on peut créer facilement une fonction lambda pour appliquer à toutes les listes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
sansdoublon = lambda ens: [elem for i, elem in enumerate(ens) if elem not in ens[:i]]
e = sansdoublon(e1)
print e
[1, 2, 3, 4, 5, 6]

Puisque tu ne voulais pas utiliser 'set', je te signale simplement pour mémoire la solution suivante qui utilise 'set', et qui est particulièrement simple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
print list(set(e1))
[1, 2, 3, 4, 5, 6]

Pour tester: il faut simplement utiliser 'set' pour voir si on obtient bien le même résultat! C'est d'ailleurs comme ça que j'ai vérifié mes codes du message précédent (le contrôle fait partie du codage "normal"...).

[Narlen27]

Merci beaucoup