Quels sont le nombre de permutations et la définition d'un ensemble fini ?
Cette question est une question de cours.
Une permutation est un arrangement dans un ordre spécifique des éléments d'une liste finie.
Il y a n! permutations dans un ensemble fini à n éléments.
Une permutation est un arrangement dans un ordre spécifique des éléments d'une liste finie.
Il y a n! permutations dans un ensemble fini à n éléments.
Quel est l'ensemble des permutations de l'ensemble {1,2,3} ?
Pour trouver les permutations d'un ensemble, on peut fonctionner avec l'algorithme suivant :
On fixe le premier élément de la permutation.
On génère les permutations des éléments restants (en répétant l'étape précédente).
Ici, avec trois éléments, cela signifie que l'on suit les étapes suivantes :
- Étape 1 :
Fixer le premier élément : 1
Permutations possibles : (2,3) ; (3,2)
- Étape 2 :
Fixer le premier élément : 2
Permutations possibles des éléments restants : (1,3) ; (3,1)
- Étape 3 :
Fixer le premier élément : 3
Permutations possibles des éléments restants : (1,2) ; (2,1)
Les permutations de l'ensemble {1,2,3} sont donc :
(1,2,3) ; (1;3;2) ; (2;1;3) ; (2;3;1) ; (3;1;2) ; (3;2;1)
Quel programme permet de générer les permutations d'un ensemble à 3 éléments à l'aide d'une boucle for ?
On peut réutiliser la méthode utilisée à la question précédente pour écrire cet algorithme :
Première boucle pour fixer le premier élément.
On rajoute dans les deux ordres les deux éléments restants.
Cela donne, en Python :
def permutation_3el(lst) :
l=[] #initialisation de la variable d'arrivée
assert len(lst)==3 #On s'assure que la taille de la liste est bien 3
for i in range(len(lst)) : #premières boucles sur les éléments de la liste en entrée
remLst=lst[:i] + lst[i+1:] #Création de la liste des éléments restants
l.append([lst[i],remLst[0],remLst[1]])
l.append([lst[i],remLst[1],remLst[0]]
return l
On se propose désormais d'écrire une fonction permettant de trouver les permutations de toutes les listes.
Comment compléter le code suivant aux endroits (1), (2) et (3) ?
def permutation(lst):
if len(lst) == 0 : #si lst est vide on renvoie une liste vide
return []
if len(lst)==1 : #si lst n'a qu'un élément on renvoie l'élément
return (1)
l=[] #variable qui stockera les permutation
for i in range(len(lst)) : #boucle sur les élèments de lst
m=lst[i] #On extrait un élément de la liste
remLst = (2) #Liste des éléments restants
for p in (3) :
l.append([m]+p)
return l
1) S'il n'y a qu'un seul élément dans la liste étudié, on veut de manière évidente renvoyer cette liste, donc on remplace (1) par [lst].
2) De manière analogue à la question précédente, on veut extraire tous les éléments de la liste dont on cherche les permutations à l'exception de celui à la i-ème position. Pour ceci, on remplace (2) par lst[:i]+lst[i+1:].
3) On veut que p génère une permutation de remLst car on voit qu'à l'étape suivante on crée une permutation avec l'opération l.append([m]+p).
Pour ceci, on peut tout simplement utiliser la fonction que l'on est en train de construire. De manière assez étonnante, on utilise la fonction que l'on construit à l'intérieur de cette fonction. Néanmoins, cela permet de choisir le second élément puis de générer les permutations des éléments suivants et ainsi de suite jusqu'à ce qu'il ne reste qu'un élément dans remLst.
Ainsi, on remplace (3) par permutation(remLst).
On remplace donc :
- (1) par [lst]
- (2) par lst[:i] + lst[i+1:]
- (3) par permutation(remLst)