Générer par un algorithme des permutations d'un ensemble fini Problème

Quels sont le nombre de permutations et la définition d'un ensemble fini ?

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 \begin{pmatrix} n \\ k \end{pmatrix} permutations dans un ensemble fini à n éléments.

Une permutation est un sous-ensemble à k éléments sans répétition d'un ensemble fini à n éléments.
Il y a k! permutations dans un ensemble fini à n éléments.

Une permutation est un sous-ensemble à k éléments sans répétition d'un ensemble fini à n éléments.
Il y a \begin{pmatrix} n \\ k \end{pmatrix} permutations dans un ensemble fini à n éléments.

Quel est l'ensemble des permutations de l'ensemble {1,2,3} ?

Les permutations de l'ensemble {1,2,3} sont :
(1,2,3) ; (1;3;2) ; (2;1;3) ; (2;3;1) ; (3;1;2) ; (3;2;1)

Les permutations de l'ensemble {1,2,3} sont :
(1,2,3) ; (1;1;2) ; (2;1;2) ; (2;3;3) ; (3;1;2) ; (3;2;1) ; (1;3;1) ; (2;3;3)

Les permutations de l'ensemble {1,2,3} sont :
(1,2,3) ; (1;2;2) ; (1;1;2) ; (2;2;3) ; (3;1;2) ; (1;2;1) ; (1;3;1) (2;3;3)

Les permutations de l'ensemble {1,2,3} sont :
(1,2,3) ; (3;2;1) ; (2;3;1).

Quel programme permet de générer les permutations d'un ensemble à 3 éléments à l'aide d'une boucle for ?

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]]) #Ajout des deux permutations possibles

l.append([lst[i],remLst[1],remLst[0]])

return l

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

l.append([i,remLst[0],remLst[1]])

return l

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

l.append([i]) #création de la nouvelle permutation avec le premier élément

remLst=lst[:i] + lst[i+1:] #Création de la liste des élèments restants

for j in remLst :

l[−1].append(j) #ajout à la permutation en création

return l

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

l.append([lst[i],lst[1],lst[0]])

l.append([lst[i],lst[0],lst[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

On remplace :

(1) par [lst]
(2) par lst[:i] + lst[i+1:]
(3) par permutation(remLst)

On remplace :

(1) par lst
(2) par lst[:i−1] + lst[i+1:]
(3) par permutation(remLst)

On remplace :

(1) par [lst]
(2) par lst[:i−1] + lst[i+1:]
(3) par range(len(remLst))

On remplace :

(1) par [lst]
(2) par lst[:i−1] + lst[i:]
(3) par range(len(remLst))