Génération récursive de chemins
Dans ce TP, nous allons étudier les méthodes récursives de générations d'objets combinatoires, et plus particulièrement, les chemins dans le plan.
Chemins dans le plan
On considère les deux vecteurs suivants qu'on appelle des "pas"
Un chemin est une liste de pas, par exemple :
Pour dessiner un chemin, on part de (0,0) et on se déplace selon les valeurs du vecteur. Par exemple, le chemin précédent se dessine par :
Ecrivez une fonction qui prend en paramètre un chemin et retourne le plot du chemin.
La taille d'un chemin est son nombre de pas. Le but de l'exercice est d'écrire une fonction chemins(n)
qui retourne la liste de tous les chemins de taille n.
Observez les fonctions suivantes :
En vous inspirant de la fonction chemins2
, écrivez une fonction chemins3
qui retourne la liste des chemins de taille 3.
** Sur la même idée, écrivez à présent une fonction chemins
qui prend en paramètre une taille et retourne la liste des chemins de taille **
Indication : vous devez séparer le cas des autres cas.
A présent, on va chercher à engendrer tous les chemins qui terminent en un point donné. Répondez à la question suivante :
Si je construis le chemin qui termine en en rajoutant un pas au chemin , où terminait ? Même question si le pas rajouté est .
Utilisez votre réponse pour construire une fonction récursive chemin_end_point
prenant en paramètre une abscisse et une ordonnée et qui retourne la liste des chemins partant de l'origine et terminant en .
Pour écrire votre fonction, réfléchissez aux questions suivantes : que doit retourner la fonction quand je lui demande la liste des chemins qui terminent en (0,0) ? Que doit retourner la fonction si un des points ou est négatif ? Faites bien attention à la différence entre une liste contenant le chemin vide et une liste vide de chemins !
Vérifiez sur plusieurs valeurs de et que le nombre de chemins que vous obtenez est égal à binomial(a+b,a)
.
Ecrivez à présent une fonction chemins_up_end_point
qui retourne un générateur sur les chemins terminant en et tel qu'en tout point le chemin soit au dessus de la diagonale, c'est à dire qu'on doit toujours avoir .
Selon cette contrainte, combien obtenez-vous de chemins qui terminent en ?
Comptez les chemins qui terminent en pour , vous devez trouver 1, 2, 5, 14, 42, 132. Cherchez ces nombres sur Google.
Les Nombres de Catalans sont des objets classiques de la combinatoires. Parcourez la page wikipedia et voyez si trouvez dans Sage certains des objets décrits.
Aller plus loin : vous pouvez continuer les expériences sur les chemins en faisant varier les pas possibles et contraintes. Lorsque vous obtenez une suite de nombres, vous pouvez regarder sur http://oeis.org/ si elle correspond à des objets combinatoires connus.