É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.

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.

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    

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.

def permutation(L):
    pmt = []
    permute(L, 0, pmt)
    return pmt