Quelle est la définition d'une permutation et quel est le nombre de permutations d'un ensemble fini à n éléments distincts ?
On peut répondre directement à cette question grâce au cours :
Une permutation d'un ensemble fini est un réarrangement des objets distincts de l'ensemble de départ.
Il y a n! permutations d'un ensemble à n éléments distincts.
Une permutation d'un ensemble fini est un réarrangement des objets distincts de l'ensemble de départ.
Il y a n! permutations d'un ensemble à n éléments distincts.
On se propose de générer aléatoirement une permutation d'un élément fini.
On rappelle que la fonction randint(debut,fin) du module random permet de générer aléatoirement un nombre entier compris entre debut et fin.
La fonction list.pop(index) permet de supprimer l'élément à l'indice index de la liste tout en le renvoyant en sortie.
Comment compléter les espaces (1) et (2) du code suivant ?
from random import randint
def permutalea(L):
sortie=[] #on initialise la liste de sortie qui sera une permutation de L
for i in (1) : #on réalise autant d'étapes qu'il y a d'éléments dans L
sortie.append((2)) #On ajoute un élément de L au hasard dans sortie
return sortie
(1) On voit qu'à l'intérieur de la boucle, à chaque itération, on ne rajoute qu'un seul élément à la variable sortie. Or, une permutation d'un ensemble à n éléments est aussi constitué de n éléments. Ainsi, il faut passer n fois dans la boucle, avec n la taille de la liste d'entrée. On remplace (1) par range(len(L)).
La fonction range() permet en effet de générer une liste allant de 0 à len(L)-1 donc à n éléments.
(2) Pour constituer une permutation au hasard, on veut récupérer un à un les éléments de la liste d'entrée, sans répétition et dans un ordre aléatoire.
Afin de ne pas avoir de répétition, on va utiliser la méthode de liste : .pop(). Elle permettra de retirer de la liste L les éléments déjà utilisés.
Afin de générer l'indice de l'élément au hasard, on va utiliser la fonction randint(debut, fin) qui permet de générer aléatoirement un entier compris entre debut et fin.
Finalement, on remplace (2) par L.pop(randint(0,len(L)-1)).
Ainsi, à chaque itération, on génère un indice des éléments restants dans la liste L, que l'on retire de L et que l'on rajoute à la variable sortie.
On remplace donc :
- (1) par range(len(L))
- (2) par L.pop(randint(0, len(L)-1))
Dans un jeu concours, l'organisateur réalise un tirage aléatoire de 5 boules numérotées de 1 à 5. Il réalise l'expérience durant 7 jours consécutifs.
Quel algorithme renvoie une liste des résultats des 7 jours avec la fonction permutalea(L) ?
Chaque jour, le présentateur qui réalise le tirage va en fait aléatoirement constituer une permutation de la liste [1,2,3,4,5].
On peut ainsi faire une boucle qui répétera durant les 7 jours l'expérience et tirera aléatoirement une nouvelle permutation.
L'algorithme qui renvoie une liste des résultats des 7 jours avec la fonction permutalea(L) est donc :
def tirage() :
sortie=[] #initialisation de la variable de sortie
for i in range(7) :
sortie.append(permutalea([1,2,3,4,5])
return sortie