<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 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 
Step1:  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.
Step2:  Pour récupérer les objets de stupid_generator, il faut le transformer explicitement en liste ou alors parcourir les objets à travers une boucle.
Step3:  Remarque 
Step5:  Exercice 
Step6:  Votre fonction doit passer les tests suivants 
Step7:  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.
Step10:  Exercice
Step11:  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.
Step12:  Les fonctions suivantes génèrent les mots binaires de taille 0,1, et 2.
Step14:  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.
Step16:  Sur le même modèle, implanter la fonction suivante. (un peu plus dur)
Posez-vous la question de cette façon 
Step18:  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 
Step19:  Exécutez la ligne suivante et copiez la liste des nombres obentus dans Google.
<ASSISTANT_TASK:>
Python Code:
def stupid_generator(end):
    i = 0
    while i < end:
        yield i
        i+=1
stupid_generator(3)
Explanation: 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.
End of explanation
def stupid_list(end):
    i = 0
    result = []
    while i < end:
        result.append(i)
        i+=1
    return result
stupid_list(3)
Explanation: 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.
End of explanation
it = stupid_generator(3)
it.next()
list(stupid_generator(3))
for v in stupid_generator(3):
    print v
Explanation: Pour récupérer les objets de stupid_generator, il faut le transformer explicitement en liste ou alors parcourir les objets à travers une boucle.
End of explanation
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
it = test_generator()
it.next()
it.next()
it.next()
it.next()
Explanation: 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.
End of explanation
def first_fibonacci_generator(n):
    
    Return a generator for the first ``n`` Fibonacci numbers
    
    # write code here
Explanation: 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$.
End of explanation
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])
Explanation: Votre fonction doit passer les tests suivants :
End of explanation
def powers2():
    v = 1
    while True:
        yield v
        v*=2
for v in powers2():
    print v
    if v > 1000000:
        break
Explanation: 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.
End of explanation
def fibonacci_generator():
    
    Return an infinite generator for Fibonacci numbers
    
    # write code here
it = fibonacci_generator()
it.next()
def fibonacci_finder(n):
    
    Return the first Fibonacci number greater than or equal to n
    
    # write code here
assert(fibonacci_finder(10) == 13)
assert(fibonacci_finder(100) == 144)
assert(fibonacci_finder(1000) == 1597)
assert(fibonacci_finder(1000000) == 1346269)
Explanation: Exercice: Implantez les fonctions suivantes
End of explanation
binaires1 = ["0", "1"]
binaires2 = ["00", "01", "10", "11"]
Explanation: 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.
End of explanation
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"
list(binary_word_generator2())
Explanation: Les fonctions suivantes génèrent les mots binaires de taille 0,1, et 2.
End of explanation
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
list(binary_word_generator(3))
# 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)
Explanation: 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.
End of explanation
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
list(binary_kword_generator(4,2))
# 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)
Explanation: 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é
End of explanation
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
list(dyck_prefix_generator(4,2))
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)
Explanation: 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.
End of explanation
[len(set(dyck_prefix_generator(2*n, n))) for n in xrange(8)]
Explanation: Exécutez la ligne suivante et copiez la liste des nombres obentus dans Google.
End of explanation
<END_TASK>