Vous êtes ici : Accueil Tutoriels Utilité de la combinatoire dans la vraie vie

Utilité de la combinatoire dans la vraie vie

La combinatoire est une notion que certain d'entre nous ont touché du doigt en étudiant les probabilités en terminale et oublié une fois le bac en poche. Aussi, on les utilise rarement, alors qu'il s'agit d'outils qui trouvent parfaitement leur place en algorithmique : la combinatoire nous permet de simplifier largement notre code.

Avant propos

Pour illustrer la combinatoire, nous allons utiliser un exemple dans lequel on souhaite insérer des données dans une base de données SQL. Le but de ce tutoriel n'étant pas la méthodologie SQL, on restera succint sur ce sujet. On admet simplement que l'on s'est créé un curseur et que l'on exécute les requêtes directement à partir de lui.

Voici le schéma de la base qui servira d'exemple.

+--------+   +----------+   +------------+   +-------+   +----------------+
| acteur |<--| role |-->| personnage |-->| piece |<--| representation |
+--------+ +----------+ +------------+ +-------+ +----------------+
| > id | | id_a | | > id | | > id | | > id |
| > nom | | id_perso | | > id_piece | | > nom | | > id_piece |
| | | | | > nom | | | | > date |
| | | | | | | | | > lieu |
| | | | | | | | | > numéro |
| | | | | | | | | > nb_inscrits |
+--------+ +----------+ +------------+ +-------+ +----------------+

itertools.repeat

Voici un algorithme classique pour rajouter deux pièces et plusieurs personnages :

cursor.execute('insert into piece (nom) values (?)', "L'assassin est dans la salle")
id_piece = cursor.lastrowid

for nom in ['commissaire', 'stagiaire']:
    cursor.execute('insert into personnage (id_piece, nom) values (?, ?)', [id_piece, nom])

L'algorithme fonctionne parfaitement. Mais il n'est pas optimisé. En effet, pour rajouter une pièce et X personnages, il faudra X+1 requêtes, alors que deux suffiraient en utilisant un insert multiple pour l'ajout des personnages. Mais pour cela, il faut construire au préalable le tableau de données à passer en paramètre.

On peut alors recourir classiquement à une compréhension de liste. L'algorithme devient :

cursor.execute('insert into piece (nom) values (?)', "L'assassin est dans la salle")
id_piece = cursor.lastrowid

cursor.executemany('insert into personnage (id_piece, nom) values (?, ?)', [(id_piece, nom) for nom in ['commissaire', 'stagiaire']])

Si l'on veut encore optimiser un peu, on peut utiliser un générateur en lieu et place de la compréhension de liste :

cursor.executemany('insert into personnage (id_piece, nom) values (?, ?)', [(id_piece, nom) for nom in ['commissaire', 'stagiaire']))

Mais voilà, lorsqu'il y a plus de colonnes, on peut se trouver rapidement limité avec ces techniques (ou s'en sortir en écrivant du code difficile à relire). C'est là qu'intervient la combinatoire. En effet, on a d'un coté un champs qui référence la pièce et qu'il va falloir répéter et d'un autre coté une liste de noms. L'idée est donc de répéter le premier champs autant de fois que nécessaire 

from itertools import repeat
datas = [repeat(id_piece), ['commissaire', 'stagiaire']]

On se retrouve avec deux listes dont chaque colonne représente un champs et chaque ligne un enregistrement à effectuer. Il ne suffit donc plus que de pivoter la liste pour obtenir ce que l'on souhaite :

from itertools import repeat
cursor.execute('insert into piece (nom) values (?)', "L'assassin est dans la salle")
id_piece = cursor.lastrowid

cursor.executemany('insert into personnage (id_piece, nom) values (?, ?)', zip(repeat(id_piece), ['commissaire', 'stagiaire']))

On voit ainsi rapidement ce qu'il reste à faire pour rajouter des données d'autres colonnes. Si ces données sont identiques pour toutes les lignes, il faut utiliser à nouveau repeat, sinon, il faut rajouter une liste de la même longueur que la liste des noms (et présentée dans le même ordre, cela va sans dire). Ainsi, on peut ajouter très facilement des représentations. Ainsi, ) partir de ces données  :

dates = ['2012-10-01', '2012-10-03', '2012-10-05']
lieux = ['Rodez', 'Millau', 'Toulouse']
numéros = [1, 2, 3]
nombre = 0

On peut écrire cela 

cursor.executemany('insert into representation (id_piece, date, lieu, numéro, nb_inscrits) values (?, ?, ?, ?, ?)', zip(repeat(id_piece), dates, lieux, numéros, repeat(nombre)))

Mais à partir de ce simple dictionnaire: :

reprs = {
    '2012-10-01': 'Rodez',
    '2012-10-03': 'Millau',
    '2012-10-05': 'Toulouse',
}

On peut écrire :

cursor.executemany('insert into representation (id_piece, date, lieu, numéro, nb_inscrits) values (?, ?, ?, ?, ?)', zip(repeat(id_piece), reprs.keys(), reprs.values(), range(1, len(reprs)+1), repeat(0)))

Le tout n'utilisant que des générateurs !

itertools.product

La fonctionnalité repeat est parfaitement utile pour rajouter des enregistrements à partir de relations 1..n, mais pour en rajouter avec des relations n..n, il faut utiliser la notion de produit.

Ainsi, la documentation nous explique basiquement ceci :

>>> from itertools import product
>>> list(product('AB', [1, 2]))
[('A', 1), ('A', 2), ('B', 1), ('B', 2)]

C'est ce dont nous avons besoin pour rajouter des rôles, par exemple.

Nous avons déjà créé des personnages dont les identifiants sont contenus dans la variable perso_ids. Considérons que nous avons créé de la même manière des acteurs dont les identifiants sont contenus dans la variable acteur_ids. Voici la méthode à suivre avec un algorithme classique :

for id_p in perso_ids:
    for id_a in acteur_ids:
        cursor.execute('insert into role (id_a, id_p) values (?, ?)', (id_a, id_p))

Il est possible d'utiliser un insert multiple en construisant la donnée au préalable :

datas = []
for id_p in perso_ids:
    for id_a in acteur_ids:
        data.append((id_a, id_p))

cursor.executemany('insert into role (id_a, id_p) values (?, ?)', datas)

L'utilisation de itertools.product permet de se passer de tout ce travail fastidieux :

from itertools import product
cursor.executemany('insert into role (id_a, id_p) values (?, ?)', product(acteur_ids, perso_ids))

Et voilà le travail !

Conclusion

En espérant que ce petit tutoriel va vous permettre d'apprécier à nouveau la combinatoire et de changer votre manière d'écrire des algorithmes, je vous invite à fouiller le module itertools et à essayer de l'utiliser dans cos développements. Il est une pure merveille, encore plus grâce au fait que Python 3 ne travaille plus qu'avec des générateurs. Dans la même veine, il y a également le module functools dont la découverte est plus ardue, mais qui devient rapidement indispensable.

Spinner