Formation I.S.N.

Sous-ensembles

Exercice : les parties d'un ensemble

On décide de représenter un ensemble par une liste (sans doublon).

Par exemple, un ensemble de couleurs :


	 L = ['jaune', 'vert', 'bleu', 'orange', 'magenta', 'marron', 'brun', 'rouge' ]

Écrire une fonction python récursive :

Entrée Un ensemble sous la forme précédente.
Sortie L'ensemble des parties de cet ensemble.
  • définition récursive
  • un code
  • Cas de base : lorsqu'un ensemble E est vide, l'ensemble des parties de E est constitué du seul sous-ensemble vide.
  • Dans les autres cas, on peut écrire E sous la forme de la réunion d'un ensemble F et d'un singleton {a}. L'ensemble des parties de E est alors constitué des parties Q de F et des parties Q ∪ {a}. 

def parties(L) :
	if L == [] : return [[]]
	else : 
		p = parties(L[1:])  
		return p + [ [L[0]] + partie for partie in p]
	
	
L = ['jaune', 'vert', 'bleu', 'orange', 'magenta', 'marron', 'brun', 'rouge' ]
P = parties(L)
print( P) 
n = len(L)
print("Nombre d'éléments de la liste initiale L : ", n)
print(" 2^{} = {}.".format( n, 2**n ) )
print("Nombre d'éléments dans parties(L) : ", len(P) )

Complément Python

Le langage python offre la possibilité suivante :


from itertools import combinations


L = ['jaune', 'vert', 'bleu', 'rouge' ]

for i in range(len(L)) :
	print(list(combinations(L,i)))

Consulter la documentation.

Complément python

En langage python, on peut utiliser les types set et frozenset pour les ensembles.

Consulter la doc ou cette page de tutoriel.