TP_Recurs.sagews

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"

step0 = (1,0)
step1 = (0,1)
︠82b47fdd-f1ba-47e0-a6a1-c5eb4b6ee3d1i︠
%html
<p>
    Un chemin est une liste de pas, par exemple :
</p>

Un chemin est une liste de pas, par exemple :

chemin = [step0,step0,step1,step0]
chemin
︠5225515b-6733-4250-b99e-c950824827f3i︠
%html
<p>
    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 :
</p>

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 :

line2d([(0,0),(1,0),(2,0),(2,1),(3,1)])
︠9609ac47-e8ce-4fc9-9977-6eba9303f28fi︠
%html
<p>
    <strong>Ecrivez une fonction qui prend en paramètre un chemin et retourne le plot du chemin. </strong> 
</p>

Ecrivez une fonction qui prend en paramètre un chemin et retourne le plot du chemin.

︠3d302c37-972e-4e83-81c0-283b9933745d︠

︠50e55a45-4498-44d6-af31-f8753a13d188i︠
%md
La taille d'un chemin est son nombre de pas. Le but de l'exercice est d'écrire une fonction <code>chemins(n)</code> qui retourne 
**la liste de tous les chemins de taille n**. 

Observez les fonctions suivantes :

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 :

def chemins0():
    R = []
    R.append([]) # un chemin de taille 0 est une liste vide
    return R
    
def chemins1():
    R = []
    R.append([(1,0)]) # on ajoute les 2 chemins de taile 1 posible
    R.append([(0,1)])
    return R
    
def chemins2():
    R = []
    for chemin in chemins1():
        chemin_a = list(chemin)  # on copie le chemin
        chemin_a.append((1,0)) # on lui ajoute le pas (1,0)
        chemin_b = list(chemin) # on copie le chemin
        chemin_b.append((0,1)) # on lui ajoute le pas (0,1)
        R.append(chemin_a) # on ajoute les deux chemins  au résultat
        R.append(chemin_b)
    return R
︠435451a9-3a2a-4fff-9127-b791852908b2︠
chemins2()
︠82c07ad7-93da-4ef8-976f-051d0d3414ad︠

︠8202c00f-9014-4486-8a64-2dbe09017c52i︠
%md
**En vous inspirant de la fonction <code>chemins2</code>, écrivez une fonction <code>chemins3</code> qui retourne la liste des chemins de taille 3**.

En vous inspirant de la fonction chemins2, écrivez une fonction chemins3 qui retourne la liste des chemins de taille 3.

def chemins3():
    """
    Retourne la liste des chemins de taille 3
    """
    # écrire le code ici
︠04cad636-25a7-42f3-9f77-8c087ef864df︠
# quelques tests que doit valider votre fonction: si tout va bien, rien ne s'affiche !
R = chemins3()
assert(len(R) == 8)
assert([(1,0),(0,1),(0,1)] in R)
︠d7da5562-34ea-48b7-aca7-f73b785aef2c︠

︠82492354-4fb1-4caf-8924-7e5146abef16i︠
%md
** Sur la même idée, écrivez à présent une fonction <code>chemins</code> qui prend en paramètre une taille $n$ et retourne la liste des chemins de taille $n$ **

Indication : vous devez séparer le cas $n=0$ des autres cas.

** Sur la même idée, écrivez à présent une fonction chemins qui prend en paramètre une taille $n$ et retourne la liste des chemins de taille $n$ **

Indication : vous devez séparer le cas $n=0$ des autres cas.

def chemins(n):
    """
    Retourne la liste des chemins de taille n
    """
    # écrire le code ici
︠f2d53dd7-9212-4e79-9cc0-bbf12c907c66︠
# quelques tests que doit valider votre fonction: si tout va bien, rien ne s'affiche !
assert(chemins(0) == [[]])
assert(len(chemins(1)) == 2)
assert(len(chemins(2)) == 4)
C1 = chemins(3)
C2 = chemins3()
C1.sort()
C2.sort()
assert(C1 == C2)
assert(len(chemins(4)) == 16)
︠3b5a9900-79f4-4649-b820-a03cd7e18aaf︠
︠04c68735-b32f-4aa6-a0d3-50aaaa56685f︠
︠ee294448-972f-441f-964c-c5d9e0843d6e︠

︠deed9f19-910b-4946-8592-5824bc5fb1fci︠
%html
<p>
    A présent, on va chercher à engendrer tous les chemins qui terminent en un point $(a,b)$ donné. Répondez à la question suivante :
    <br />
    <strong>Si je construis le chemin $c$ qui termine en $(a,b)$ en rajoutant un pas $(1,0)$ au chemin $c'$, où terminait $c'$ ? Même question si le pas rajouté est $(0,1)$.</strong>
</p>

A présent, on va chercher à engendrer tous les chemins qui terminent en un point $(a,b)$ donné. Répondez à la question suivante :
Si je construis le chemin $c$ qui termine en $(a,b)$ en rajoutant un pas $(1,0)$ au chemin $c'$, où terminait $c'$ ? Même question si le pas rajouté est $(0,1)$.

Utilisez votre réponse pour construire une fonction récursive chemin_end_point prenant en paramètre une abscisse $a$ et une ordonnée $b$ et qui retourne un générateur sur les chemins partant de l'origine et terminant en $(a,b)$.

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 $a$ ou $b$ est négatif ? Faites bien attention à la différence entre une liste contenant le chemin vide et une liste vide de chemins !

def chemins_end_point(a,b):
    """
    Retourne la liste des chemins terminant au point (a,b)
    """
    # écrire le code ici
︠32347ccf-c6ef-47aa-ac78-839b4c855a25s︠
# quelques tests que doit valider votre fonction: si tout va bien, rien ne s'affiche !
assert(chemins_end_point(0,0) == [[]])
assert(chemins_end_point(-1,0) == [])
assert(chemins_end_point(0,-2) == [])
assert(chemins_end_point(1,0) == [[(1,0)]])
assert(chemins_end_point(0,1) == [[(0,1)]])
assert(len(chemins_end_point(3,5)) == binomial(8,3))

︠391d5c8b-f706-40b2-ae2c-cc4d86d4e639i︠
%html
<p>
    <strong>Vérifiez sur plusieurs valeurs de $a$ et $b$ que le nombre de chemins que vous obtenez est égal à <code>binomial(a+b,a)</code>.</strong>
</p>

Vérifiez sur plusieurs valeurs de $a$ et $b$ que le nombre de chemins que vous obtenez est égal à binomial(a+b,a).

︠ba06336a-e4e2-4f31-b902-55470a32bada︠

︠17c5f787-adf2-4190-8d0f-7cd0b52a590fi︠
%html 
<p>
    <strong>Ecrivez à présent une fonction <code>chemins_up_end_point</code> qui retourne un générateur sur les chemins terminant en $(a,b)$ et tel qu'en tout point le chemin soit au dessus de la diagonale, c'est à dire qu'on doit toujours avoir $b\geq a$.</strong>
</p>

Ecrivez à présent une fonction chemins_up_end_point qui retourne un générateur sur les chemins terminant en $(a,b)$ et tel qu'en tout point le chemin soit au dessus de la diagonale, c'est à dire qu'on doit toujours avoir $b\geq a$.

def chemins_up_end_point(a,b):
    """
    Retourne la liste des chemins terminant au point (a,b)
    tels que le chemin reste au dessus de la dagonal (b >= a)
    """
    # écrire le code ici
︠59e16ad5-d476-46e3-8a2a-038c7e93962b︠
# quelques tests que doit valider votre fonction: si tout va bien, rien ne s'affiche !
assert(chemins_up_end_point(0,0) == [[]])
assert(chemins_up_end_point(-1,0) == [])
assert(chemins_up_end_point(0,-2) == [])
assert(chemins_up_end_point(1,0) == [])
assert(chemins_up_end_point(0,1) == [[(0,1)]])
assert(len(chemins_up_end_point(3,3)) == 5)
assert(len(chemins_up_end_point(4,4)) == 14)
︠aadbda09-8367-44f7-a6c3-6e162de964cf︠
︠7d991511-0399-4344-a520-f98de4f16c13︠

︠50f4ca45-08f1-4275-b3ad-c235fd6b693d︠

︠de2a4b5b-1f87-482c-96fc-98fa2fad3c98i︠
%html
<p>
    <strong>Selon cette contrainte, combien obtenez-vous de chemins qui terminent en $(5,5)$ ?</strong>
</p>

Selon cette contrainte, combien obtenez-vous de chemins qui terminent en $(5,5)$ ?

︠4f8e6fb1-dd55-437e-9354-7b2459bb26f4i︠
%html
<p>
    <strong>Comptez les chemins qui terminent en $(n,n)$ pour $1 \leq n \leq 6$, vous devez trouver 1, 2, 5, 14, 42, 132. Cherchez ces nombres sur Google.</strong>
</p>

Comptez les chemins qui terminent en $(n,n)$ pour $1 \leq n \leq 6$, vous devez trouver 1, 2, 5, 14, 42, 132. Cherchez ces nombres sur Google.

︠4da4d8fa-a857-4565-88f4-28857b75e5cci︠
%html
<p>
    <strong>Les <em>Nombres de Catalans</em> sont des objets classiques de la combinatoires. Parcourez la page wikipedia et voyez si trouvez dans Sage certains des objets décrits.</strong> 
</p>

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.

︠3e30ed9b-4d08-45af-80e4-2f919c1f2eddi︠
%html
<p>
    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 <a href="http://oeis.org/" >http://oeis.org/</a> si elle correspond à des objets combinatoires connus. 
</p>

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.