Ce TP est une introduction à la notion de génération récursive d'objets combinatoires.
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)
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)]
In [ ]: