Page 65 - Activités algorithmiques avec Python en spécialité Mathématiques

Thème : combinatoire & probabilités
TI-83 Premium CE Edition Python TI-82 Advanced Edition Python
Niveau : spécialité maths Terminale
La combinatoire des parties
L. DIDIER & R. CABANE
Fiche méthode
Objectif 1 : la liste des parties
La logique à suivre est de considérer le premier élément s[0] de l’ensemble s (ici pris comme une chaîne de caractères) et de distinguer les parties contenant cet élément de celles qui ne le contiennent pas.
Une fois que ce choix est effectué, il n’y a plus qu’à « recom-
mencer de même » sur les éléments restants, ce qui se note On utilise ici des « listes en compréhension »,
s[1:] ; nous avons ici une fonction récursive ! syntaxe concise permettant de créer le résultat à partir des éléments d’une liste.
Pour que cela s’achève, il faut traiter préalablement les cas où
l’ensemble possède 0 ou 1 élément (l’ensemble à 1 élément admet
deux parties, la partie vide et la partie pleine). Le principe de récur-
sivité montre, au passage, que le nombre de parties double quand
on ajoute un élément à l’ensemble ; en d’autres termes, le nombre
n de parties d’un ensemble à n éléments est 2 .
Objectif 2 : la liste des combinaisons
Commençons par un cas très simple, suggéré par le programme : lister les sous-ensembles de taille 2 d’un ensemble donné. Cela peut se faire de manière très simple en Python grâce au principe des « listes en compréhension », voir ci-contre.
On pourrait procéder de même pour les parties à trois éléments, mais la commande commence à être pénible à écrire, aussi convient-il de chercher une réponse plus générale. Si on s’autorise à écrire une fonction doublement récursive, on peut suivre un peu la même idée que pour le listage de toutes les parties : celles qui contiennent le premier élément et celles qui ne le contiennent pas.
Il faut prendre garde à l’initialisation et bien prévoir les deux cas extrêmes : lorsqu’on ne cherche que des parties vides (en ce cas, on renvoie le vide sous la forme ['']), et lorsqu’on ne cherche que la partie pleine (en ce cas, on renvoie s pour seule réponse).
Détail à surveiller : le symbole + désigne ici la concaténation (mise bout à bout) dans deux contextes différents :
▸ l’expression s[0]+u est une chaîne de caractères, commençant par s[0] et continuant avec u, ▸ et l’opération + qui suit concatène deux listes.
Nous reviendrons plus loin sur l’inefficacité de ce codage (défi « modérer la récursivité »).
Ce document est mis à disposition sous licence Creative Commons 63 © Texas Instruments 2021 / Photocopie autorisée