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 generateur, le langage python possède une instruction très pratique pour créer des générateurs : yield.


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

In [ ]:
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 [ ]:
def stupid_list(end):
    i = 0
    result = []
    while i < end:
        result.append(i)
        i+=1
    return result

In [ ]:
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 [ ]:
it = stupid_generator(3)

In [ ]:
it.next()

In [ ]:
list(stupid_generator(3))

In [ ]:
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 dexuième objet, l'exécution sera reprise là où elle a été arrétée.


In [ ]:
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 [ ]:
it = test_generator()

In [ ]:
it.next()

In [ ]:
it.next()

In [ ]:
it.next()

In [ ]:
it.next()

Exercice : implanter la fonction suivante dont le but est de générer les n premiers nombre de Fibonacci La suite de fibonacci est définie par :

$f_0 = 0$

$f_1 = 1$

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


In [ ]:
def first_fibonacci_generator(n):
    """
    Return a generator for the first ``n`` Fibonacci numbers
    """
    # write code here

In [ ]:


In [ ]:

Votre fonction doit passer les tests suivants :


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

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 [ ]:
def powers2():
    v = 1
    while True:
        yield v
        v*=2

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

Exercice: Implantez les fonctions suivantes


In [ ]:
def fibonacci_generator():
    """
    Return an infinite generator for Fibonacci numbers
    """
    # write code here

In [ ]:
it = fibonacci_generator()

In [ ]:
it.next()

In [ ]:
def fibonacci_finder(n):
    """
    Return the first Fibonacci number greater than or equal to n
    """
    # write code here

In [ ]:


In [ ]:
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 [ ]:
binaires1 = ["0", "1"]
binaires2 = ["00", "01", "10", "11"]

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


In [ ]:
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 [ ]:
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 [ ]:
def binary_word_generator(n):
    """
    Return a generator on binary words of size n in lexicographic order
    
    Input :
        - n, the length of the words
    """
    # write code here

In [ ]:
list(binary_word_generator(3))

In [ ]:
# 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)

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.

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


In [ ]:
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
    """
    # write code here

In [ ]:
list(binary_kword_generator(4,2))

In [ ]:


In [ ]:
# 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 [ ]:
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
    """
    # write code here

In [ ]:
list(dyck_prefix_generator(4,2))

In [ ]:
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 obentus dans Google.


In [ ]:
[len(set(dyck_prefix_generator(2*n, n))) for n in xrange(8)]

Aller plus loin

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


In [ ]: