Dans cet exercice, on étudie les combinaisons à k éléments d'un ensemble à n éléments distincts.
Quelle est la définition d'une combinaison et quel est le nombre de combinaison à k éléments d'un ensemble de n éléments distincts ?
On peut répondre à cette question grâce au cours.
Il faut tout d'abord vérifier que k \leq n.
Une combinaison de k éléments d'un ensemble à n éléments est un sous-ensemble sans répétition et sans ordre de l'ensemble de départ.
Il y a \begin{pmatrix} n \\ k \end{pmatrix} combinaisons à k éléments d'un ensemble à n éléments.
Une combinaison de k éléments d'un ensemble à n éléments est un sous-ensemble sans répétition de l'ensemble de départ.
Il y a \begin{pmatrix} n \\ k \end{pmatrix} combinaisons à k éléments d'un ensemble à n éléments.
On se propose d'étudier un algorithme permettant d'obtenir les combinaisons à 2 éléments d'un ensemble fini de nombres réels.
Comment compléter l'algorithme suivant ?
def generation_parties(L)
n=len(L)
assert (1) #On s'assure qu'il y ait plus de deux éléments dans la liste
return [(2)]
(1) On veut s'assurer qu'il y a plus de 2 éléments dans la liste d'entrée donc on remplace (1) par n>=2.
(2) On veut retourner l'ensemble des combinaisons à 2 éléments de l'ensemble de départ, et ce en une seule ligne. On va ici utiliser les compréhensions de liste, qui permettent de parcourir des listes avec des conditions et ce sur une seule ligne.
La syntaxe est la suivante : result for element in liste if condition
Dans le cas étudié, on veut renvoyer une combinaison à deux éléments de la liste de départ L sans qu'il y ait de répétitions donc on remplace (2) par : [a,b] for a in L for b in L if a<b
En effet, on veut un duo de deux éléments de L.
On s'assure de ne pas avoir de répétition grâce à la condition a<b.
On remplace donc :
- (1) par n>=2
- (2) par [a,b] for a in L for b in L if a<b
On veut désormais compléter la fonction précédente en lui donnant un nouveau paramètre m.
- Si m=2 on veut les combinaisons à 2 éléments de la liste.
- Si m=3 on veut les combinaisons à 3 éléments de la liste.
Comment écrire la nouvelle fonction generation_parties(L,m) ?
Pour écrire la nouvelle fonction generate_parties(L,m), on va rajouter une boucle conditionnelle qui va permettre de faire deux actions différentes en fonction de la valeur de m.
Pour renvoyer les combinaisons à 3 éléments de la liste L, on utilise exactement la même méthode que pour les combinaisons à 2 éléments.
def generate_parties(L,m) :
n=len(L)
assert n>=m #on s'assure que la liste contient plus d'éléments que la taille des combinaisons recherchées.
if m==2 :
return [(a,b) for a in L for b in L if a<b] #si on demande les combinaisons à deux éléments on renvoie les combinaisons comme à la question précédente
elif m==3 :
return [(a,b,c) for a in L for b in L for c in L if a<b<c] #si on demande les combinaisons à trois éléments on utilise la même méthode en incluant une nouvelle variable c
La nouvelle fonction s'écrit donc :
def generate_parties(L,m) :
n=len(L)
assert n>=m
if m==2 :
return [(a,b) for a in L for b in L if a<b]
elif m==3 :
return [(a,b,c) for a in L for b in L for c in L if a<b<c]