====== Énumération des permutations d'une liste ======

On prend une liste, par exemple ''L = [1, 2, 3]'', et on voudrait donner la liste de toutes les « permutations » que l'on peut faire.

Par exemple, pour ''L = [1, 2, 3]'', on obtiendrait ''%%[[1, 2, 3], [2, 3, 1], [3, 1, 2], [1, 3, 2], [3, 2, 1], [2, 1, 3]]%%''.

On utilise pour cela un algorithme récursif.

  * Pour une liste qui ne contient qu'un élément, il n'y a rien à faire.\\ si ''L=[1]'' alors on obtient ''%%[[1]]%%''.
  * Si une liste contient ''n > 1'' éléments,
    * on considère les ''n'' listes ''Li'' obtenues en permutant ''L[0]'' avec ''L[i]''
    * on détermine toutes les permutations en ne considérant que les items de rangs ''2:n'',

Exemple pour ''n = 3'', ''L = [A, B, C]'',
  * On détermine ''L0 = [A, B, C]'', ''L1 = [B, A, C]'', ''L3 = [B, C, A]''
  * pour ''L0'' on obtient les permutations ''%%[[A, B, C], [A, C, B]]%%''
  * pour ''L1'' on obtient les permutations ''%%[[B, A, C], [B, C, A]]%%''
  * pour ''L2'' on obtient les permutations ''%%[[C, B, A], [C, A, B]]%%''
On a ainsi obtenu toutes les permutations possibles de ''[A, B, C]''.

Il y a donc **récursivité** puisque pour obtenir les permutations de ''n'' items, on doit calculer les permutations de ''n-1'' items.

===== fonction récursive =====

Pour l'implémentation de cet algorithme en Python, on commence par créer une fonction récursive ''permute(L, i, result)'' qui permute les éléments de la liste ''L'' en laissant fixes les éléments d'indices strictement inférieurs à ''i'' et ajoute à la liste ''result'' des permutations déjà obtenues la nouvelle permutation ainsi créée.

On remarquera que lorsque ''i == len(L)-1'', on se contente d'ajouter ''L'' à ''result''.

<code lang-none linenums:1>
FONCTION permute
ENTRÉES:
  L: liste dont on veut les permutations
  i: les items de rang <= i restent à leur place
  result: tableau, collecte les permutations trouvées
DÉBUT
  soit n le nombre d'items de L
  SI i est n - 1 ALORS
    ajouter L au bout de result
  FIN
  POUR j allant de i à n-1 FAIRE
    permuter les items de rang i et j dans L
    
    ... complétez
    
    permuter les items de rang j et i dans L
  FIN
FIN    
</code>

===== fonction qui amorce la récurrence =====

Dans une fonction ''permutations(L)'' on initialise la liste attendue des permutations à ''pmt = []'', puis on lance ''permute(L, 0, pmt)'' et on retourne ''pmt'' en fin du processus récursif.

<code python>
def permutation(L):
    pmt = []
    permute(L, 0, pmt)
    return pmt
</code>


<WRAP box>**À faire :** Faites l'implémentation et testez.</WRAP>