<jupyter_start><jupyter_text>Arbres binairesLe but de ce TP est d'implanter les fonctions usuelles telles que la *génération exhaustive* (fabriquer tous les éléments de l'ensemble), *rank* et *unrank* sur l'ensemble des [arbres binaires](https://fr.wikipedia.org/wiki/Arbre_binaire).  Pour représenter les arbres binaires en python, on utilisera la structure suivante.**Exécutez les cellules suivantes et observez les exemples**.<jupyter_code>class BinaryTree():
    
    def __init__(self, children = None):
        """
        A binary tree is either a leaf or a node with two subtrees.
        
        INPUT:
            
            - children, either None (for a leaf), or a list of size excatly 2 
            of either two binary trees or 2 objects that can be made into binary trees
        """
        self._isleaf = (children is None)
        if not self._isleaf:
            if len(children) != 2:
                raise ValueError("A binary tree needs exactly two children")
            self._children = tuple(c if isinstance(c,BinaryTree) else BinaryTree(c) for c in children)
        self._size = None
        
    def __repr__(self):
        if self.is_leaf():
            return "leaf"
        return str(self._children)
    
    def __eq__(self, other):
        """
        Return true if other represents the same binary tree as self
        """
        if not isinstance(other, BinaryTree):
            return False
        if self.is_leaf():
            return other.is_leaf()
        if other.is_leaf():
            return False
        return self.left() == other.left() and self.right() == other.right()
    
    
    def left(self):
        """
        Return the left subtree of self
        """
        return self._children[0]
    
    def right(self):
        """
        Return the right subtree of self
        """
        return self._children[1]
    
    def is_leaf(self):
        """
        Return true is self is a leaf
        """
        return self._isleaf
    
    def _compute_size(self):
        """
        Recursively computes the size of self
        """
        if self.is_leaf():
            self._size = 0
        else:
            self._size = self.left().size() + self.right().size() + 1
    
    def size(self):
        """
        Return the number of non leaf nodes in the binary tree
        """
        if self._size is None:
            self._compute_size()
        return self._size
    
    def height(self):
        if self._isleaf:
            return 0
        else:
            aux_left = self.left()
            height_left = aux_left.height()
            aux_right = self.right()
            height_right = aux_right.height()
            return 1+max(height_left, height_right)
        
leaf = BinaryTree()
        
t = BinaryTree((leaf, leaf))
t
t.size()
t = BinaryTree([[leaf,leaf], leaf]) # a tree of size 2
t
t.size()
t = BinaryTree([leaf, [leaf,leaf]]) # a different tree of size 2
t
t.size()
t = BinaryTree([[leaf, leaf], [leaf, leaf]]) # a tree of size 3
t
t.size()<jupyter_output><empty_output><jupyter_text>Il y a 5 arbres binaires de taille 3. L'un deux est celui que nous venons de construire. **Construisez explicitement les 4 autres**<jupyter_code>t1 = BinaryTree([[leaf, leaf], [leaf, leaf]])
t1
t2 = BinaryTree([[leaf, [leaf, leaf]], leaf])
t2.size()
t3 = BinaryTree([leaf, [leaf, [leaf, leaf]]])
t3.size()
t4 = BinaryTree([[[leaf, leaf], leaf], leaf])
t4.size()<jupyter_output><empty_output><jupyter_text>Le but de ce TP est d'implanter les fonctions de la classe `BinaryTrees` ci-dessous (avec un "s" à la fin) qui représente *l'ensemble* des arbres binaires d'une taille donnée. La structure de la classe vous est donnée ainsi que les méthodes de base.**Complétez les méthodes manquantes puis exécutez les exemples ci-dessous.**<jupyter_code>import math
import random
class BinaryTrees():
    
    def __init__(self, size):
        """
        The combinatorial set of binary trees of size `size`
        
        INPUT:
        
            - size a non negative integers
        """
        self._size = size
        
    def size(self):
        """
        Return the size of the binary trees of the set
        """
        return self._size
    
    def __repr__(self):
        """
        Default string repr of ``self``
        """
        return "Binary Trees of size " + str(self._size)
    
    def cardinality(self):
        """
        Return the cardinality of the set
        """
        # This is given to you
        n = self._size
        f = math.factorial(n)
        return math.factorial(2*n)/(f*f*(n+1))
    
    def __iter__(self):
        """
        Iterator on the elements of the set
        """
        # write code here
        if not self._size:
            yield BinaryTree()
        else:
            if self._size == 1:
                yield BinaryTree([leaf, leaf])
            else:
                for i in range(self._size):
                    for t1 in BinaryTrees(i):
                        for t2 in BinaryTrees(self._size - i - 1):
                            yield BinaryTree([t1, t2])
                    
    def first(self):
        """
        Return the first element of the set 
        """
        for t in self:
            return t
                    
    def rank(self,t):
        """
        Return the rank of the binary tree t in the generation order of the set (starting at 0)
        
        INPUT:
        
            - t, a binary tree
        """
        # write code here
        cont = 0
        for arbre in self:
            if arbre == t:
                return cont
            else:
                cont += 1
    
    def unrank(self,i):
        """
        Return the binary tree corresponding to the rank ``i`` 
        
        INPUT:
        
            - i, a integer between 0 and the cardinality minus 1
        """
        # write code here
        cont = 0
        for t in self:
            if cont == i:
                return t
            else:
                cont += 1
        
        
    def next(self,t):
        """
        Return the next element following t in self
        
        INPUT :
        
            - t a binary tree
            
        OUPUT :
        
        The next binary tree or None if t is the last permutation of self
        """
        # write code here
        trank = self.rank(t)
        if trank + 1 == self.cardinality():
            return None
        else:
            nextrank = trank + 1
            return self.unrank(nextrank)
    
    def random_element(self):
        """
        Return a random element of ``self`` with uniform probability
        """
        # write code here
        tounrank = random.randint(0,self.cardinality()-1)
        return self.unrank(tounrank)
BinaryTrees(0)
list(BinaryTrees(0))
BinaryTrees(1)
list(BinaryTrees(1))
BinaryTrees(2)
list(BinaryTrees(2))
BT3 = BinaryTrees(3)
BT3
list(BT3)
t = BinaryTree(((leaf, leaf), (leaf, leaf)))
BT3.rank(t)
BT3.unrank(2)
BT3.next(t)
BT3.random_element()<jupyter_output><empty_output><jupyter_text>La suite de tests que nous avions définies sur les permutations peut aussi s'appliquer sur les arbres binaires. **Exécutez la cellule suivante puis vérifiez que les tests passent sur les exemples**.<jupyter_code>def test_cardinality_iter(S):
    assert(len(list(S)) == S.cardinality())

def test_rank(S):
    assert([S.rank(p) for p in S] == range(S.cardinality()))
    
def test_unrank(S):
    assert(list(S) == [S.unrank(i) for i in xrange(S.cardinality())])
    
def test_next(S):
    L = [S.first()]
    while True:
        p = S.next(L[-1])
        if p == None:
            break
        L.append(p)
    assert(L == list(S))
            
    
def all_tests(S):
    tests = {"Cardinality / iter": test_cardinality_iter, "Rank": test_rank, "Unrank": test_unrank, "Next": test_next}
    for k in tests:
        print "Testsing: "+ k
        try:
            tests[k](S)
            print "Passed"
        except AssertionError:
            print "Not passed"
all_tests(BinaryTrees(3))
all_tests(BinaryTrees(4))
all_tests(BinaryTrees(5))
all_tests(BinaryTrees(6))<jupyter_output>Testsing: Next
Passed
Testsing: Cardinality / iter
Passed
Testsing: Rank
Passed
Testsing: Unrank
Passed<jupyter_text>Voici une fonction qui calcule un arbre binaire aléatoire. On se demande si chaque arbre est obenu avec une probabilité uniforme.**Exécutez les cellules ci-dessous puis déterminez expérimentalment si la distribution de probabilité est uniforme**.<jupyter_code>import random
def random_grow(t):
    """
    Randomly grows a binary tree 
    
    INPUT:
    
        - t, a binary tree of size n
        
    OUTPUT: a binary tree of size n+1
    """
    if t.is_leaf():
        return BinaryTree([leaf,leaf])
    c = [t.left(),t.right()]
    i = random.randint(0,1)
    c[i] = random_grow(c[i])
    return BinaryTree(c)

def random_binary_tree(n):
    """
    Return a random binary tree of size n
    """
    t = leaf
    for i in xrange(n):
        t = random_grow(t)
    return t
random_binary_tree(10)
aux = BinaryTrees(5)
dist = [0]*aux.cardinality()
for index in range(1000):
    newt = random_binary_tree(5)
    rankt = aux.rank(newt)
    dist[rankt] += 1
print dist<jupyter_output>[0, 0, 4, 0, 0, 7, 11, 11, 9, 3, 1, 1, 0, 2, 30, 37, 131, 30, 40, 98, 97, 90, 92, 30, 34, 121, 23, 39, 2, 0, 6, 0, 0, 11, 16, 6, 11, 0, 0, 5, 1, 1]<jupyter_text>La *hauteur* d'un arbre se calcule récursivement : pour une feuille, la hauteur est 0, sinon c'est le max de la hauteur des fils +1. **Rajoutez une méthode `height` à la classe des arbres binaires et vérifiez son fonctionnement avec les tests suivants**.<jupyter_code>assert BinaryTree([[leaf,leaf], leaf]).height() == 2
assert BinaryTree([leaf,[leaf, leaf]]).height() == 2
assert BinaryTree([[leaf,leaf], [leaf,leaf]]).height() == 2
assert BinaryTree([[leaf,[leaf,leaf]], [leaf,leaf]]).height() == 3<jupyter_output><empty_output><jupyter_text>**Calculez la hauteur moyenne de 100 arbres aléatoire de tailles 10, 100 et de 10 arbres aléatoires de taille 500, d'abord avec la méthode uniforme (de la classe `BinaryTrees`) puis avec la fonction `random_trees` interprétez le résultat**<jupyter_code>cor = {10:0, 100:1, 500:2}
height_uniform = [0]*3
height_random = [0]*3
Bin10 = BinaryTrees(10)
Bin100 = BinaryTrees(100)
Bin500 = BinaryTrees(500)
for i in range(100):
    height_uniform[0] += Bin10.random_element().height()
    height_random[0] += random_binary_tree(10).height()
height_uniform[0] /= 100.
height_random[0] /= 100.
for i in range(100):
    height_uniform[1] += Bin100.random_element().height()
    height_random[1] += random_binary_tree(100).height()
height_uniform[1] /= 100.
height_random[1] /= 100.
for i in range(10):
    height_uniform[2] += Bin500.random_element().height()
    height_random[2] += random_binary_tree(500).height()
height_uniform[2] /= 10.
height_random[2] /= 10.<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11026928343222273, 'fraction_numerical': 0.02190780465540849, 'mean_word_length': 2.228049499116087, 'pattern_counts': {'":': 4, '<': 27, '<?xml version=': 0, '>': 27, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '344506', 'license': 'MIT', 'n_tokens_mistral': 3676, 'n_tokens_neox': 3452, 'n_words': 1077, 'path': 'TP3BinaryTrees.ipynb', 'repo_name': 'gustavo-castro/grammargen', 'size': '10955'}