Les itérateurs combinatoires sont des outils qui fournissent des blocs de construction pour rendre le code plus efficace. Cette introduction vous montre quelques-unes des plus utiles en Python.
Compter les choses
Dans cet article, je voudrais fournir une brève introduction aux itérateurs combinatoires en Python.
La combinatoire au sens mathématique consiste à compter des choses. Cela peut nous aider à compter le nombre de permutations de quelque chose (combien d'arrangements possibles d'un jeu de cartes) ou le nombre de combinaisons (combien d'arrangements uniques de boules de couleurs différentes). Pour que cela fonctionne, nous avons besoin d'une collection d'objets sur lesquels agir - quelque chose à parcourir.
En Python, les objets itérables, plus communément appelés itérables , sont des groupes de données. Certains itérables courants que vous connaissez peut-être sont les listes, les tuples, les ensembles et les tableaux, que vous pouvez parcourir à l'aide d'une boucle for. Ces itérables sont généralement remplis de valeurs entières, de flottants ou de chaînes. Une chaîne elle-même est un itérable puisque vous pouvez parcourir tous les caractères qu'elle contient. Un concept connexe est un itérateur , qui est un objet qui renvoie l'élément suivant d'un itérable.
En rassemblant ces deux éléments, nous nous retrouvons avec des itérateurs combinatoires. Ils vous aident à compter les choses :par exemple, différentes combinaisons de nombres dans une liste ou différentes permutations d'une chaîne. La fonctionnalité pour vous aider à faire tout cela est fournie dans le module itertools, qui est fourni avec l'installation par défaut de Python.
Avant d'entrer dans les détails des itérateurs combinatoires en Python, il vaut la peine d'examiner de plus près comment parcourir un itérable. Si vous êtes un débutant complet en Python, consultez ce cours qui est conçu pour répondre aux besoins des personnes sans expérience en programmation.
Itérateurs, itérables et itération
Nous avons dit que les itérables sont des groupes de données - une liste d'entiers, par exemple. Mais pour obtenir les éléments individuels d'une liste, nous avons besoin d'un itérateur. Si vous êtes intéressé par les détails, consultez la documentation Python. Nous pouvons définir une liste avec des valeurs entières comme suit :
x = [1, 2, 3]
Il est important de noter que lorsque vous faites cela, la liste entière est enregistrée en mémoire. Pour parcourir cette liste, l'approche standard consiste à utiliser un for boucle, mais il existe un autre moyen d'utiliser certaines des fonctions intégrées moins connues de Python, en particulier iter() et next() . Vous pouvez définir l'itérable directement dans le iter() méthode et imprimez les éléments comme suit :
>>> x_iterator = iter([1, 2, 3]) >>> print(next(x_iterator)) 1 >>> print(next(x_iterator)) 2 >>> print(next(x_iterator)) 3 >>> print(next(x_iterator)) StopIteration
Ici, nous avons créé un itérateur x_iterator avec le type <class 'list_iterator'> , parmi les [1, 2, 3] itérables avec le type <class 'list'> . Cet itérateur peut être considéré comme un flux d'entiers venant les uns après les autres. Pour accéder aux entiers, nous utilisons le next() intégré méthode pour l'itérer, une valeur à la fois. Une fois accédé, l'entier est supprimé du flux et le nombre d'itérations est stocké sous forme de variable interne, ce qui permet à l'itérateur de se souvenir de sa place lorsque le next() méthode est appelée à nouveau. Une fois l'itération terminée, elle lève un StopIteration exception, puisque tous les éléments ont été supprimés. Cela signifie que l'itérateur ne peut être parcouru qu'une seule fois.
À ce stade, vous vous demandez peut-être comment les boucles for se rapportent à tout cela, puisque c'est ainsi que l'itération est normalement effectuée. En effet, un for loop est un type d'itérateur. Avant l'exécution d'une boucle for, un objet itérateur est créé en arrière-plan, puis l'itération est effectuée jusqu'au StopIteration exception se présente. Pour ceux d'entre vous qui ont besoin d'un rappel sur les boucles for, consultez cet article. Donc, avec un for boucle, l'itération peut être réalisée par :
>>> x_iterator = iter([1, 2, 3]) >>> for element in x_iterator: ... print(element)
Notez que nous devons redéfinir x_iterator puisque nous avons déjà atteint le StopIteration dans le premier exemple. C'est la différence entre parcourir la liste x directement et itérer à travers x_iterator . Toute la liste x est stocké en mémoire et peut être itéré à plusieurs reprises, alors que x_iterator est un flux d'entiers qui ne peut être itéré qu'une seule fois. Par conséquent, en utilisant x_iterator est plus efficace, et cela commence vraiment à porter ses fruits lorsqu'il s'agit de traiter une grande quantité de données.
Les itérateurs itertools
Comme son nom l'indique, le itertools Le module fournit des outils pour travailler avec des itérables et des itérateurs. Vous pouvez trouver la documentation ici. Il existe de nombreuses fonctions dans ce module, qui appartiennent toutes à l'une des trois catégories :les itérateurs infinis (pensez à un while boucle), terminant les itérateurs (pensez à un for boucle) et itérateurs combinatoires (compter les choses).
Ils sont conçus pour économiser la mémoire, de sorte que les fonctions de ce module renvoient des itérateurs qui fournissent les résultats dans un flux de données. Étant donné que les données ne sont produites que lorsque cela est nécessaire, les itérables n'ont pas besoin d'être stockés en mémoire. Cela peut être un peu déroutant, alors voyons quelques exemples concrets de la façon d'appeler ces fonctions et de récupérer les résultats. Les fonctions que nous allons examiner sont de type combinatoire et peuvent être utiles pour rendre votre code plus efficace.
produit()
Le premier des itertools les fonctions que nous allons examiner sont product() , qui implémente le produit cartésien de deux itérables. Le mécanisme de fonctionnement est illustré ci-dessous dans la figure et revient à créer un tableau 2D à partir de deux vecteurs 1D. Les entrées peuvent être n'importe quel itérable et la sortie est donnée sous la forme d'une liste de tuples. Si vous voulez un vrai tableau, vous devez reformuler la sortie, par exemple en utilisant NumPy.
Produit cartésien de (x, y, z) x (1, 2, 3)
Pour implémenter cela en Python, appelez simplement la fonction depuis itertools comme ci-dessous :
>>> result = itertools.product(['x', 'y', 'z'], [1, 2, 3])
La variable de résultat est maintenant un itérateur de type <class 'itertools.product'> . C'est essentiellement le même que le x_iterator de l'exemple précédent, et en tant que tel, ne peut être itéré qu'une seule fois en utilisant soit une boucle for soit le next() méthode. Alternativement, vous pouvez le reformuler sous forme de liste, à quel point le résultat entier est stocké en mémoire et peut être itéré plusieurs fois .
>>> result_list = list(result)
Notez également que les entrées sont une liste de chaînes et une liste d'entiers. La liste résultante de tuples conserve ces types de données. Cette fonction peut également être utilisée pour calculer le produit cartésien d'un itérable avec lui-même, en utilisant l'argument optionnel repeat. Les deux lignes ci-dessous donnent le même résultat :
>>> itertools.product(['x', 'y', 'z'], repeat=2) >>> itertools.product(['x', 'y', 'z'], ['x', 'y', 'z'])
Essayez de résoudre ce problème sans le itertools bibliothèque et voyez ce que vous proposez. La solution la plus évidente est d'utiliser deux for loops, et boucle à travers chaque élément dans les deux listes, nécessitant 3 lignes de code. Au lieu de cela, ce problème simple est résolu beaucoup plus efficacement avec le product() fonction.
permutations()
Une permutation est un arrangement d'objets dans un ordre particulier. Vous souvenez-vous de l'exemple de jeu de cartes de l'introduction ? Combien y a-t-il d'arrangements différents dans un jeu de 52 cartes, et à quoi ressemblent-ils ?
En pratique, le calcul de ces permutations en Python n'est pas simple. Pour 52 cartes, il y en a 52 ! (environ 8 x 10 67 ) permutations. C'est un nombre si important que, chaque fois que vous prenez un jeu de cartes bien mélangé, vous détenez probablement un arrangement qui n'a jamais existé auparavant et n'existera plus jamais ! Alors s'il vous plaît, n'essayez pas de calculer cela à la maison - si vous le faites, votre ordinateur ne vous en remerciera pas.
Considérons un problème plus facile à résoudre, où nous pouvons calculer des permutations en Python. Combien y a-t-il d'arrangements possibles de trois boules de couleurs différentes, et à quoi ressemblent-elles ?
>>> balls = itertools.permutations(['red', 'green', 'blue'])
>>> for permutation in balls:
... print(permutation)
...
('red', 'green', 'blue')
('red', 'blue', 'green')
('green', 'red', 'blue')
('green', 'blue', 'red')
('blue', 'red', 'green')
('blue', 'green', 'red')
Il y a 3! =3 x 2 x 1 =6 permutations. Cela peut également être calculé en refondant les boules sous forme de liste et en obtenant la longueur avec le len() fonction intégrée. Essayez par vous-même. Si vous souhaitez en savoir plus sur certaines des fonctions intégrées les plus utiles de Python, consultez ce cours.
combinaisons()
La fonction suivante fournit des fonctionnalités pour calculer des combinaisons en Python. Cela diffère légèrement des permutations en ce que l'ordre des éléments n'est pas important lors de l'examen des combinaisons. Il existe un argument de mot clé supplémentaire, r , qui définit la longueur des combinaisons à rechercher.
Reprenons notre exemple avec les boules colorées et ajoutons une jaune à la liste :
>>> balls = itertools.combinations(['red', 'green', 'blue', 'yellow'], r=3)
Le mot clé r=3 dit que nous sommes intéressés à envisager des combinaisons de 3 boules, dont il y en a 4, comme indiqué ci-dessous :
>>> for combination in balls:
... print(combination)
...
('red', 'green', 'blue')
('red', 'green', 'yellow')
('red', 'blue', 'yellow')
('green', 'blue', 'yellow')
combinaisons_avec_remplacement()
Comme son nom l'indique, cette fonction suivante est similaire à combinations() , mais cela permet aux éléments d'être répétés plus d'une fois . Cela se traduit par de nombreuses autres combinaisons possibles. Nous allons donc vous montrer un sous-ensemble ci-dessous, mais vérifiez vous-même la liste complète :
>>> balls = itertools.combinations_with_replacement(['red', 'green', 'blue', 'yellow'], r=3)
>>> for combination in balls:
... print(combination)
...
('red', 'red', 'red')
('red', 'red', 'green')
('red', 'red', 'blue')
...
('blue', 'blue', 'yellow')
('blue', 'yellow', 'yellow')
('yellow', 'yellow', 'yellow')
Un défi de codage
Les exemples ci-dessus avec des boules colorées montrent comment certains des itertools les fonctions fonctionnent, mais elles sont un peu sèches. Il est donc temps pour un exemple plus pertinent.
Lorsque vous postulez à des emplois en programmation, les responsables du recrutement envoient souvent un défi de codage aux candidats pour tester leurs compétences. Pour ceux d'entre vous à la recherche d'emplois dans le domaine de la technologie, voici un article utile. Considérons un problème plus intéressant que vous pourriez rencontrer lors de votre prochaine candidature et voyons comment itertools peut être appliqué.
Énoncé du problème :"De combien de manières pouvez-vous changer un billet de 100 $ en utilisant n'importe quel nombre de billets de 50 $, 20 $ et 10 $ ?"
Une approche naïve consiste à générer manuellement des combinaisons de 2 notes, 3 notes, 4 notes, etc., et de vérifier si leur somme est égale à 100. Ceci est sujet aux erreurs et ressemble à une salade de for boucles, while boucles, et if-else déclarations. Mais sachant que le plus grand nombre possible de billets est 10 (10 $ x 10 =100 $) et que l'expression "n'importe quel nombre" implique un remplacement, vous pouvez générer une solution plus efficace qui ressemble à ceci :
>>> notes = [50, 20, 10] >>> result = [] >>> for i in range(1, 11): ... for combination in itertools.combinations_with_replacement(notes, i): ... if sum(combination) == 100: ... result.append(combination) ... >>> print(len(result)) 10
Comme nous l'avons montré, en utilisant itertools peut aider à calculer les produits cartésiens, les permutations et les combinaisons en Python. Cela simplifie grandement votre code en réduisant votre dépendance aux boucles et aux instructions conditionnelles. Ce qui pourrait prendre plusieurs lignes peut être fait en une seule. Cela rend le code plus simple, plus lisible et plus efficace.
C'est déjà une victoire, mais le niveau suivant arrive lorsque vous commencez à utiliser itertools fonctionne comme des blocs de construction pour créer des expressions combinées pour des algorithmes basés sur des itérations plus complexes. Python a également des itérateurs intégrés qui peuvent être utilisés en conjonction avec itertools pour réaliser ce prochain niveau de programmation.
Voulez-vous plus d'Itertools ?
Nous n'avons parlé que de 4 fonctions de cette bibliothèque. Cela vaut la peine de jeter un coup d'œil au itertools documentation pour avoir une meilleure idée de ce que cette bibliothèque peut faire. Si vous souhaitez mettre la main sur plus de itertools , essayez le module bien nommé more-itertools. Celui-ci n'est pas fourni avec Python - vous devrez donc l'installer vous-même, mais il regorge de fonctions utiles qui vous faciliteront sûrement la vie à un moment donné de votre parcours Python.
