Génération récursive

Ce TP est une introduction à la notion de génération récursive d'objets combinatoires.

Le Yield python

Cette section est une introduction à la notion de générateurs en Python qui nous sera utilie par la suite.

Vous avez vu en cours le principe d'un générateur. Le langage python possède une instruction très pratique pour créer des générateurs : yield.



In [1]:

    
def stupid_generator(end):
    i = 0
    while i < end:
        yield i
        i+=1



In [2]:

    
stupid_generator(3)

Le but de la fonction stupid_generator est de lister les entiers inférieurs à end. Cependant, elle ne retourne pas directement la liste mais un générateur sur cette liste. Comparez avec la fonction suivante :



In [3]:

    
def stupid_list(end):
    i = 0
    result = []
    while i < end:
        result.append(i)
        i+=1
    return result



In [4]:

    
stupid_list(3)

Pour récupérer les objets de stupid_generator, il faut le transformer explicitement en liste ou alors parcourir les objets à travers une boucle.



In [5]:

    
it = stupid_generator(3)



In [8]:

    
next(it)



In [9]:

    
list(stupid_generator(3))



In [11]:

    
for v in stupid_generator(3):
    print(v)

Remarque : les instructions de stupid_generator ne sont pas exécutées lors de l'appel initial de la fonction mais seulement lorsque l'on commence à parcourir le générateur pour récupérer le premier objet. L'instruction yield stoppe alors l'exécution et retourne le premier objet. Si l'on demande un deuxième objet, l'exécution sera reprise là où elle a été arrétée.



In [13]:

    
def test_generator():
    print("Cette instruction est exécutée lors de l'appel du premier objet")
    yield 1
    print("Cette instruction est exécutée lors de l'appel du deuxième objet")
    yield 2
    print("Cette instruction est exécutée lors de l'appel du troisième objet")
    yield 3



In [14]:

    
it = test_generator()



In [15]:

    
next(it)



In [16]:

    
next(it)



In [17]:

    
next(it)



In [19]:

    
next(it) # l'appel de next sur un générateur terminé lève une exception

Exercice : implanter la fonction suivante dont le but est d'engendrer les n premiers nombre de Fibonacci.

La suite de fibonacci est définie par :

$f_0 = 1$

$f_1 = 1$

$f_n = f_{n-1} + f_{n-2}$ pour $n \geq 2$.

Remarques :

La fonction doit renvoyer l'ensemble des nombres de Fibonacci, pas seulement le dernier.
Pour cette raison (et pour d'autres), une version itérative est largement préférable à une récursive. Ne vous inquiétez pas, on fera plein de récursivité après !
Vous n'avez pas non non plus besoin d'un tableau pour stocker toute la suite, 3 variables sont suffisantes.



In [1]:

    
def first_fibonacci_generator(n):
    """
    Return a generator for the first ``n`` Fibonacci numbers
    """
    # écrire le code ici



In [4]:

    
it = first_fibonacci_generator(5)
it



In [9]:

    
next(it)

Votre fonction doit passer les tests suivants :



In [2]:

    
import types
assert type(first_fibonacci_generator(3)) == types.GeneratorType
assert list(first_fibonacci_generator(0)) == []
assert list(first_fibonacci_generator(1)) == [1]
assert list(first_fibonacci_generator(2)) == [1,1]
assert list(first_fibonacci_generator(8)) == [1,1,2,3,5,8,13,21]

Dans les cas précédent, le générateur s'arrête de lui même au bout d'un certain temps. Cependant, il est aussi possible d'écrire des générateurs infinis. Dans ce cas, la responsabilité de l'arrêt revient à la l'appelant.



In [23]:

    
def powers2():
    v = 1
    while True:
        yield v
        v*=2



In [24]:

    
for v in powers2():
    print(v)
    if v > 1000000:
        break

Exercice: Implantez les fonctions suivantes



In [25]:

    
def fibonacci_generator():
    """
    Return an infinite generator for Fibonacci numbers
    """
    # écrire le code ici



In [26]:

    
it = fibonacci_generator()



In [30]:

    
next(it)



In [31]:

    
def fibonacci_finder(n):
    """
    Return the first Fibonacci number greater than or equal to n
    """
    # écrire le code ici



In [ ]:



In [32]:

    
assert fibonacci_finder(10) == 13
assert fibonacci_finder(100) == 144
assert fibonacci_finder(1000) == 1597
assert fibonacci_finder(1000000) == 1346269

Mots binaires

Nous allons nous intéresser à la génération récursive de mots binaires vérifiants certaines propriétés. Nous allons représenter les mots binaires par des chaines de carcatères, par exemples.



In [33]:

    
binaires1 = ["0", "1"]
binaires2 = ["00", "01", "10", "11"]

Les fonctions suivantes génèrent les mots binaires de taille 0,1, et 2.



In [34]:

    
def binary_word_generator0():
    yield ""
    
def binary_word_generator1():
    yield "0"
    yield "1"
    
def binary_word_generator2():
    for b in binary_word_generator1():
        yield b + "0"
        yield b + "1"



In [35]:

    
list(binary_word_generator2())

En vous inspirant des fonctions précédentes (mais sans les utiliser) ou en reprenant la fonction du cours, implantez de façon récursive la fonction suivante qui engendre l'ensemble des mots binaires d'une taille donnée.



In [36]:

    
def binary_word_generator(n):
    """
    Return a generator on binary words of size n in lexicographic order
    
    Input :
        - n, the length of the words
    """
    # écrire le code ici



In [37]:

    
list(binary_word_generator(3))



In [38]:

    
# tests
import types
assert type(binary_word_generator(0)) == types.GeneratorType
assert list(binary_word_generator(0)) == ['']
assert list(binary_word_generator(1)) == ['0', '1']
assert list(binary_word_generator(2)) == ['00', '01', '10', '11']
assert list(binary_word_generator(3)) == ['000', '001', '010', '011', '100', '101', '110', '111']
assert len(list(binary_word_generator(4))) == 16
assert len(list(binary_word_generator(7))) == 128



In [ ]:



In [ ]:

Sur le même modèle, implanter la fonction suivante. (un peu plus dur)

Indications :

Posez-vous la question de cette façon : si j'ai un mot de taille $n$ qui termine par 0 et qui contient $k$ fois 1, combien de 1 contenait le mot taille $n-1$ à partir duquel il a été créé ? De même s'il termine par 1.
Bien que la fonction ressemble à la précédente, vous ne devez pas appeler binary_word_generator

Remarque : l'ordre des mots n'est plus imposé



In [39]:

    
def binary_kword_generator(n,k):
    """
    Return a generator on binary words of size n such that each word contains exacty k occurences of 1
    
    Input :
    
    - n, the size of the words
    - k, the number of 1
    """
    # écrire le code ici



In [40]:

    
list(binary_kword_generator(4,2))



In [ ]:



In [41]:

    
# tests
import types
assert type(binary_kword_generator(0,0)) == types.GeneratorType
assert list(binary_kword_generator(0,0)) == ['']
assert list(binary_kword_generator(0,1)) == []
assert list(binary_kword_generator(1,1)) == ['1']
assert list(binary_kword_generator(4,4)) == ['1111']
assert list(binary_kword_generator(4,0)) == ['0000']
assert set(binary_kword_generator(4,2)) == set(['0011', '0101', '1001', '0110', '1010', '1100'])
assert len(list(binary_kword_generator(7,3))) == 35

Et pour finir

On appelle un prefixe de Dyck un mot binaire de taille $n$ avec $k$ occurences de 1, tel que dans tout préfixe, le nombre de 1 soit supérieur ou égal au nombre de 0.

Par exemple : $1101$ est un préfixe de Dyck pour $n=4$ et $k=3$. Mais $1001$ n'en est pas un car dans le prefixe $100$ le nombre de 0 est supérieur au nombre de 1.



In [42]:

    
def dyck_prefix_generator(n,k):
    """
    Return a generator on binary words of size n such that each word contains exacty k occurences of 1, 
    and in any prefix, the number of 1 is greater than or equal to the number of 0.
    
    Input :
    
    - n, the size of the words
    - k, the number of 1
    """
    # écrire le code ici



In [43]:

    
list(dyck_prefix_generator(4,2))



In [44]:

    
assert len(list(dyck_prefix_generator(0,0))) == 1
assert len(list(dyck_prefix_generator(0,1))) == 0
assert len(list(dyck_prefix_generator(1,0))) == 0
assert list(dyck_prefix_generator(1,1)) == ['1']
assert set(dyck_prefix_generator(3,2)) == set(["110","101"] )
assert len(set(dyck_prefix_generator(10,5))) == 42

Exécutez la ligne suivante et copiez la liste des nombres obtenus dans Google.



In [46]:

    
[len(set(dyck_prefix_generator(2*n, n))) for n in range(8)]

Aller plus loin

Compositions

En vous inspirant de ce qui a été fait en cours reliant les compositions de $n$ (différentes façons d'écrire $n$ comme une somme d'entiers positifs) avec les mots binaires, trouvez comment vous pouvez utiliser une des fonctions écrites plus haut pour engendrer les compositions de $n$ avec un nombre de parts données.

Autres objets

Comme vous avez pu le voir, les nombres de Catalan comptent de nombreuses familles d'objets combinatoires.

Quelle famille d'objets avons-nous implantée ?
Pouvez-vous implanter les bijections entre cette famille et d'autres familles combinatoires telles que :



In [ ]: