Ce billet était initialement paru sur le blog Pydéfis.

On dispose d’une liste de 5 éléments (par exemple) et on désire tester une propriété particulière sur tous les sous-ensembles de taille 3 de cette liste. Si les objets sont numérotés de 1 à 5, on doit tester la propriété sur les objets 1,2,3 puis 1,2,4 puis 1,2,5 puis 1,3,4 puis 1,3,5 puis 1,4,5 puis 2,3,4 puis 2,3,5 puis 2,4,5 puis 3,4,5 (la propriété pourrait être, par exemple : la somme des trois nombres donne un nombre premier). Il est facile d’en dresser la liste à la main. Si en revanche il y a 20 objets et qu’on doit tester les ensembles de 5 objets exactement, il y aura alors $C_{20}^5=15 504$ séquences différentes à tester… mais le module itertools vient à la rescousse…

Énumérer avec itertools

Le module itertools de Python propose une fonction combinations qui permet d’énumérer les sous-ensembles de longueur n d’un objet itérable (et donc d’une liste) :

>>> import itertools
>>> l = [1, 2, 3, 4, 5]
>>> for p in itertools.combinations(l, 3):
   ...:     print(p)
   ...:
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)

On obtient ainsi les $C_5^3 = 10$ séquences possibles.

Tous les ensembles ayant au plus n valeurs

Si on doit maintenant énumérer les ensembles d’au plus 3 éléments, il suffit d’utiliser le même code pour chaque longueur :

import itertools
l = [1, 2, 3, 4, 5]
for long in (1, 2, 3):
    for p in itertools.combinations(l, long):
        print(p)

Si on veut obtenir un seul itérable qui permet d’énumérer ces combinaisons, on peut utiliser itertools.chain qui permet de… chaîner plusieurs itérables:

import itertools
l = [1, 2, 3, 4, 5]
for p in itertools.chain(*(itertools.combinations(l, long) for long in range(1, 4))):
    print(p)

(1,)
(2,)
(3,)
(4,)
(5,)
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 3)
(2, 4)
(2, 5)
(3, 4)
(3, 5)
(4, 5)
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)

Et si l’ordre importe ?

On pourrait avoir besoin de tester les séquences dans tous les ordres possibles : (1,2,3), puis (1,3,2) puis (2,3,1), (2,1,3), (3,1,2), (3,2,1). Le module itertools propose une fonction permutations qui fournit toutes les permutations d’un itérable particulier. On peut donc générer les séquences avec combinations puis modifier l’ordre avec permutations :

import itertools
l = [1, 2, 3, 4, 5]
for c in itertools.combinations(l, 3):
    for p in itertools.permutations(c):
        print(p)

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
(1, 2, 4)
(1, 4, 2)
(2, 1, 4)
(2, 4, 1)
(4, 1, 2)
(4, 2, 1)
(1, 2, 5)
(1, 5, 2)
(2, 1, 5)
(2, 5, 1)
(5, 1, 2)
...

Cette fois-ci, le nombre de séquences est donné par le nombre d’arrangements de 3 objets parmi 5 : $A_5^3=60$. Les 60 séquences sont bien listées par le code précédent.

Et si on autorise les doublons, les triplets etc… ?

Jusqu’ici, chaque élément de notre ensemble de 5 ne pouvait être choisi qu’une fois. Mais est-il possible d’autoriser plusieurs apparitions du même élément (tirage avec remise) ? Comme si nous piochions des numéros dans un sac, et remettions le numéro tiré dans le sac à chaque fois ?

Le module itertools propose la fonction combinations_with_replacement qui fait justement ce travail :

import itertools
l = [1, 2, 3, 4, 5]
for c in itertools.combinations_with_replacement(l, 3):
    print(c)

On obtient :

(1, 1, 1)
(1, 1, 2)
(1, 1, 3)
(1, 1, 4)
(1, 1, 5)
(1, 2, 2)
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 3)
(1, 3, 4)
(1, 3, 5)
(1, 4, 4)
(1, 4, 5)
(1, 5, 5)
(2, 2, 2)
(2, 2, 3)
(2, 2, 4)
(2, 2, 5)
(2, 3, 3)
(2, 3, 4)
(2, 3, 5)
(2, 4, 4)
(2, 4, 5)
(2, 5, 5)
(3, 3, 3)
(3, 3, 4)
(3, 3, 5)
(3, 4, 4)
(3, 4, 5)
(3, 5, 5)
(4, 4, 4)
(4, 4, 5)
(4, 5, 5)
(5, 5, 5)

Le nombre de séquences obtenues, pour 3 objets parmi 5 est donné par $\Gamma_5^3 = C_{3+5-1}^3=35$.

Des doublons, et de l’ordre ?

Dans la liste précédente figure le tirage (1,3,3), mais pas les tirage (3,1,3) et (3,3,1). Comme tout à l’heure, nous pouvons forcer l’apparition de chaque ordre. Mais attention à ne pas utiliser ici permutations() ce qui aurait pour effet de lister un peu trop de triplets (le triplet (3,3,1) apparaîtrait par exemple 2 fois… car on peut échanger l’ordre des 3…).

La liste des tirages ordonnés, avec remise, correpond à choisir un élément parmi les 5, et cela 3 fois de suite. Il y a $5^3=125$ tirages possibles, et on peut les générer avec 3 boucles imbriquées :

l = [1, 2, 3, 4, 5]
for l1 in l:
    for l2 in l:
        for l3 in l:
            print((l1, l2, l3))

On obtient bien ainsi les 125 tirages, mais ce n’est pas très joli… et obtenir 4 valeurs au lieu de 3 nécessite de changer la structure même du code (en ajoutant une boucle), ce qui n’est pas bon…

Le module itertools propose une solution avec la fonction product, qui itère sur les éléments du produit cartésien entre plusieurs itérables (ou éventuellement un seul plusieurs fois avec lui-même, ce dont nous avons besoin ici) :

import itertools
l=[1, 2, 3, 4, 5]
for c in itertools.product(l, repeat = 3):
    print(c)

Là aussi, nous obtenons bien les 125 séquences.

Énumérer sans itertools

Sans le module itertools, il est possible d’énumérer les sous-ensembles d’un ensemble de $n$ éléments en considérant l’écriture binaire des nombres de 0 à $2^n-1$. Si $n$ vaut 3, on considère donc les nombres de 0 à 7 qui s’écrivent en binaire : 000, 001, 010, 011, 100, 101, 110, 110, 111. En faisant correspondre chaque chiffre binaire à un élément (il y en a 3), un 0 indique par exemple qu’on ne prend par l’élément, et un 1 qu’on le prend. Ainsi, l’écriture 000 signifie qu’on ne prend aucun élément, 100 qu’on prend uniquement le premier, 101 qu’on prend le premier et le dernier. Énumérer les sous-ensembles revient donc à compter et à convertir les nombres en binaire.

Ces différentes techniques peuvent être utilisées dans les challenges Pydéfis) suivants :