HOWTO · Python
Comment générer toutes les permutations d’une liste en Python
Découvrez comment générer des permutations complètes ou partielles d’une liste Python avec itertools.permutations, la récursion et une approche itérative, et comprenez les doublons et la croissance factorielle.
Sur cette page
Pour générer les permutations d’une liste en Python, vous pouvez utiliser la bibliothèque standard ou choisir un algorithme récursif ou itératif si vous devez personnaliser la construction. Une permutation est un arrangement ordonné d’éléments sélectionnés : contrairement à une combinaison, l’ordre compte. Le nombre de résultats croît de manière factorielle ; générer tous les arrangements n’est donc réaliste que pour des entrées de taille modeste.
Utiliser la bibliothèque itertools
Pour la plupart des besoins, utilisez itertools.permutations. Cette fonction renvoie un itérateur de tuples, ce qui permet de traiter les résultats un par un sans créer immédiatement une liste complète. Par défaut, r correspond à la longueur de l’entrée : chaque résultat contient alors tous ses éléments. Dans l’exemple, r=2 sélectionne des paires ordonnées et la boucle parcourt toutes les longueurs de un à trois.
Avec la liste [1, 2, 3], le programme affiche :
from itertools import permutations
data = [1, 2, 3]
print("full:", list(permutations(data)))
print("length 2:", list(permutations(data, r=2)))
print("lengths 1 to 3:")
for r in range(1, len(data) + 1):
print(r, list(permutations(data, r)))
full: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
length 2: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
lengths 1 to 3:
1 [(1,), (2,), (3,)]
2 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
3 [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
L’argument r détermine le nombre d’éléments de chaque tuple. Pour obtenir toutes les longueurs non nulles, appelez la fonction une fois pour chaque valeur de r, de 1 à la longueur de la liste, comme ci-dessus. itertools.permutations distingue les éléments selon leur position : si une même valeur apparaît plusieurs fois dans l’entrée, certains tuples obtenus peuvent donc être identiques.
Consultez la documentation officielle d’itertools pour connaître la signature complète et le comportement de la fonction.
Fonction récursive pour générer des permutations
Une solution récursive choisit chaque élément à tour de rôle, puis le place devant chaque permutation des éléments restants. Le cas de base renvoie une liste contenant un unique arrangement vide ; la construction fonctionne ainsi pour toute longueur d’entrée, y compris zéro. Cette version renvoie des listes plutôt que des tuples et peut être utile pour étudier ou personnaliser la méthode.
def permute(data):
if not data:
return [[]]
result = []
for index, item in enumerate(data):
remaining = data[:index] + data[index + 1:]
for tail in permute(remaining):
result.append([item] + tail)
return result
print(permute([1, 2, 3]))
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Chaque appel récursif retire une position ; l’entrée diminue donc jusqu’à atteindre le cas de base. Des valeurs identiques situées à des positions différentes peuvent malgré tout produire des listes répétées. Cette implémentation stocke tous les résultats et effectue de nombreux appels récursifs : elle convient surtout à l’apprentissage ou aux petites entrées. Si vous n’avez pas besoin de personnaliser la construction, préférez l’itérateur de la bibliothèque standard.
Approche itérative pour générer des permutations
Vous pouvez aussi construire les résultats en insérant chaque nouvel élément à chaque position possible des arrangements partiels déjà obtenus. La liste commence par un arrangement vide, puis, à chaque étape, le nombre d’arrangements partiels est multiplié par le nombre d’éléments déjà traités : 1, puis 2, puis 3, et ainsi de suite. Cette méthode évite les appels récursifs, mais conserve tout de même l’ensemble des résultats en mémoire.
def iterative_permute(data):
results = [[]]
for item in data:
next_results = []
for ordering in results:
for index in range(len(ordering) + 1):
next_results.append(ordering[:index] + [item] + ordering[index:])
results = next_results
return results
print(iterative_permute([1, 2, 3]))
[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
L’ordre d’insertion détermine l’ordre dans lequel cette méthode renvoie les résultats, mais ne change pas les permutations produites. Choisissez-la si cette construction étape par étape correspond à votre besoin, en tenant compte de la mémoire nécessaire pour conserver tous les résultats.
Conclusion
Utilisez itertools.permutations pour obtenir un itérateur concis et paresseux, et définissez r si vous avez besoin d’une longueur précise. La récursion ou l’insertion itérative permettent de personnaliser la construction ou d’en comprendre le fonctionnement. Pour une liste de longueur n dont les positions sont distinctes, il existe n! permutations complètes : le temps de traitement et l’espace requis pour matérialiser les résultats augmentent donc rapidement. Pour les entrées plus grandes, parcourez l’itérateur au besoin ou ne générez que les longueurs et les sélections utiles à votre problème.
FAQ
-
Qu’est-ce qu’une permutation ?
C’est une sélection ordonnée d’éléments. Par exemple,[1, 2]et[2, 1]sont deux permutations différentes, car leur ordre diffère. -
Comment fonctionne
itertools.permutations?
La fonction produit des tuples de longueurrà partir de l’itérable fourni. Sirest omis, elle utilise la longueur totale de l’entrée. Les résultats sont produits à la demande, mais convertir l’itérateur en liste stocke chaque résultat. -
Que se passe-t-il si l’entrée contient des valeurs répétées ?
La fonction considère les positions, et non l’égalité des valeurs. Des valeurs répétées peuvent donc produire des tuples identiques. Convertir tous les résultats en ensemble peut éliminer les tuples répétés après leur génération si leurs éléments sont hachables, mais cela n’évite pas de les générer. Pour éviter ce travail en double, utilisez un algorithme qui ignore les choix identiques à chaque étape. -
Combien existe-t-il de permutations ?
Pournpositions distinctes, il existen!permutations de longueur complète. Si vous en choisissez seulementr, le nombre estn! / (n - r)!. -
Quelle taille d’entrée puis-je utiliser ?
Il n’existe pas de limite unique valable pour chaque machine et chaque tâche. La croissance factorielle peut rendre le traitement coûteux même pour une entrée de taille modérée, et le stockage de tous les résultats demande beaucoup de mémoire. Préférez un parcours paresseux ou une valeur derplus petite si vous n’avez pas besoin de tous les résultats complets simultanément.