HOWTO · Python
Combinaisons d'une liste en Python
Ce tutoriel montre comment trouver les combinaisons des éléments d'une liste en python
Sur cette page
Utilisez itertools.combinations() pour sélectionner un nombre fixe d’éléments sans réutiliser une position de l’entrée. Si une même position peut être sélectionnée plusieurs fois, utilisez itertools.combinations_with_replacement(). Ces deux fonctions produisent des combinaisons : l’ordre de sélection ne crée pas de nouveau résultat, contrairement aux permutations, pour lesquelles des ordres différents comptent comme des résultats distincts.
Choisir le bon type de combinaison
Choisissez une taille fixe de sélection avec combinations(), autorisez la répétition d’une position avec combinations_with_replacement(), ou générez tous les sous-ensembles avec une fonction powerset(). Les fonctions de la bibliothèque standard renvoient des itérateurs de tuples. Elles traitent l’entrée par position : des valeurs répétées à des positions différentes peuvent donc produire des tuples qui semblent identiques. L’ordre des résultats suit celui des positions dans l’entrée ; les valeurs de chaque tuple ne sont pas triées automatiquement. Pour appliquer une règle personnalisée, la récursion permet de rendre explicite le processus de sélection.
Utiliser itertools.combinations() pour des sélections sans remplacement
itertools.combinations(iterable, r) produit des tuples de longueur r sans réutiliser de position. L’itérable est parcouru dans l’ordre de l’entrée. Convertissez l’itérateur en liste si vous devez stocker ou examiner tous les résultats à la fois ; sinon, parcourez-le directement.
Exécutez cet exemple :
Le code et les libellés ou sorties affichés dans cette section restent en anglais.
from itertools import combinations
items = ["red", "blue", "green"]
for pair in combinations(items, 2):
print(pair)
Dans les résultats à deux éléments, chaque position est utilisée au plus une fois. Pour obtenir des éléments individuels, définissez r sur 1 ; pour obtenir toute l’entrée dans un seul tuple, définissez-le sur le nombre de positions de l’entrée. Si r dépasse ce nombre de positions, l’itérateur ne produit aucun résultat.
Utiliser itertools.combinations_with_replacement() lorsque les sélections peuvent se répéter
Utilisez itertools.combinations_with_replacement(iterable, r) lorsqu’il est permis de sélectionner plusieurs fois la même position de l’entrée. Cette fonction produit aussi des tuples de longueur r, selon la même règle d’ordre des positions. Par exemple, choisir des paires dans ["red", "blue"] inclut ("red", "red") et ("blue", "blue") ; combinations() omettrait ces paires. Cette méthode convient lorsqu’un choix répété a du sens, par exemple pour choisir deux boules de glace qui peuvent être du même parfum. L’argument r détermine toujours la longueur de chaque tuple.
Utiliser la récursion ou un générateur pour une implémentation personnalisée
Une fonction récursive avec retour arrière peut construire les résultats dans une liste. À chaque étape, elle ajoute une valeur, poursuit la récursion à partir de la position suivante, puis retire cette valeur afin que la boucle puisse essayer un autre choix. Un générateur suit la même logique de sélection, mais produit chaque résultat dès qu’il est trouvé. Il évite de conserver toute la collection de résultats, sauf si l’appelant la convertit explicitement en liste ; il n’est pas intrinsèquement plus rapide.
Les deux fonctions personnalisées ci-dessous exigent que r soit un entier non négatif et lèvent ValueError dans le cas contraire. Avec r = 0, chacune renvoie l’unique tuple vide ; si r est positif et supérieur au nombre de positions de l’entrée, aucune ne produit de résultat. Le générateur vérifie son argument au début de l’itération, car le corps d’une fonction génératrice s’exécute de manière différée.
Le code et les libellés ou sorties affichés dans cette section restent en anglais.
def get_combinations(items, r):
if not isinstance(r, int) or isinstance(r, bool) or r < 0:
raise ValueError("r must be a nonnegative integer")
results = []
def backtrack(start, chosen):
if len(chosen) == r:
results.append(tuple(chosen))
return
for index in range(start, len(items)):
chosen.append(items[index])
backtrack(index + 1, chosen)
chosen.pop()
backtrack(0, [])
return results
def generate_combinations(items, r):
if not isinstance(r, int) or isinstance(r, bool) or r < 0:
raise ValueError("r must be a nonnegative integer")
if r == 0:
yield ()
return
for index in range(len(items)):
for suffix in generate_combinations(items[index + 1 :], r - 1):
yield (items[index],) + suffix
items = ["red", "blue", "green"]
print(get_combinations(items, 2))
print(list(generate_combinations(items, 2)))
Pour créer une version personnalisée différée, utilisez yield lorsque la sélection est complète. Dans les deux implémentations, faites avancer l’appel récursif suivant à index + 1 afin d’éviter de réutiliser une position. Si l’entrée contient des valeurs répétées, certains résultats peuvent sembler identiques même s’ils proviennent de positions différentes.
Générer tous les sous-ensembles avec une fonction powerset()
Un ensemble des parties contient des sous-ensembles de toutes les tailles, y compris le tuple vide et l’entrée complète. Cette implémentation rassemble les résultats obtenus pour chaque taille possible. chain.from_iterable() renvoie un itérateur : enveloppez-le dans list() uniquement si vous devez matérialiser tous les sous-ensembles.
Le code et les libellés ou sorties affichés dans cette section restent en anglais.
from itertools import chain, combinations
def powerset(items):
values = list(items)
return chain.from_iterable(
combinations(values, size) for size in range(len(values) + 1)
)
for subset in powerset(["red", "blue"]):
print(subset)
Pour n positions dans l’entrée, un ensemble des parties contient 2**n sous-ensembles. Ce nombre augmente rapidement ; préférez donc un itérateur de combinaisons de taille fixe si la tâche ne demande que des sélections d’une seule taille. Utilisez l’ensemble des parties lorsque le résultat doit réellement contenir des sous-ensembles de toutes les tailles.