Correspondance de Łukasiewicz (2)

Suite de l'exercice précédent

Dans l'exercice précédent, on a construit une fonction qui renvoie un chemin pour un arbre enraciné donné.

Ici, il s'agit de la fonction réciproque, ce qui établit une correspondance entre arbre enraciné et chemin de Łukasiewicz.

Méthode approximative

Comment faire sur cet exemple ?

1. Le chemin est bien dans le quadrant en haut à droite.
2. Le chemin est associé à une liste de valeurs [2, -1, 4, -1, 1, -1, -1, -1, -1, -1]
3. On ajoute \(1\) à chaque élément, et on ajoute \(0\) à la fin de la liste. On obtient [3, 0, 5, 0, 2, 0, 0, 0, 0, 0, 0]
4. La difficulté est ici ; le découpage. Il y a 3 sous arbres à la racine.
   • Le découpage est 3, [0], [5, 0, 2, 0, 0, 0, 0, 0], [0].
   • Le découpage de [5, 0, 2, 0, 0, 0, 0, 0] est 5, [0], [2, 0, 0], [0], [0], [0].
   • Enfin, le découpage de [2, 0, 0] est 2, [0], [0]
5. Les [0] obtenus sont les feuilles de l'arbre.

Programmer le découpage est délicat.

Écrire une fonction chemin_vers_arbre qui implémente l'autre partie de la correspondance de Łukasiewicz.

Exemples

qui correspond à la liste [1, -1], donne un arbre

représenté en interne avec [[], []].

🐍 Console Python

>>> chemin_vers_arbre([1, -1])
[[], []]

qui correspond à la liste [2, -1, -1, 1, -1], donne un arbre

représenté en interne avec [[], [], [[], []]].

🐍 Console Python

>>> chemin_vers_arbre([2, -1, -1, 1, -1])
[[], [], [[], []]]

###

Lancer# testsbksl-nlbksl-nlassert cheminpy-undverspy-undarbre([1, -1]) == [[], []]bksl-nlbksl-nlassert cheminpy-undverspy-undarbre([2, -1, -1, 1, -1]) == [[], [], [[], []]]bksl-nlbksl-nl# autres testsbksl-nlbksl-nlassert cheminpy-undverspy-undarbre([]) == []bksl-nlassert cheminpy-undverspy-undarbre([0]) == [[]]bksl-nlassert cheminpy-undverspy-undarbre([0, 0, 0, 0]) == [[[[[]]]]]bksl-nlassert cheminpy-undverspy-undarbre([2, -1, -1]) == [[], [], []]bksl-nlassert cheminpy-undverspy-undarbre([4, -1, -1, -1, -1]) == [[], [], [], [], []]bksl-nlassert cheminpy-undverspy-undarbre([2, 0, -1, 4, -1, -1, -1, 0, -1, -1]) == [[[]], [[], [], [], [[]], []], []]bksl-nlbksl-nl Valider ∞/∞ TéléchargerTéléverser RechargerSauvegarder

def cheminpy-undverspy-undarbre(chemin):bksl-nl "correspondance de Łukasiewicz"bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert cheminpy-undverspy-undarbre([1, -1]) == [[], []]bksl-nlbksl-nlassert cheminpy-undverspy-undarbre([2, -1, -1, 1, -1]) == [[], [], [[], []]]bksl-nlbksl-nldef cheminpy-undverspy-undarbre(chemin):bksl-nl "correspondance de Łukasiewicz"bksl-nl def etape(temp, i):bksl-nl "Fonction récursive interne"bksl-nl if temp[i] == 0:bksl-nl return [], 1bksl-nl else:bksl-nl resultat = []bksl-nl taillepy-undtotale = 1bksl-nl for py-und in range(temp[i]):bksl-nl souspy-undarbre, taille = etape(temp, i + taillepy-undtotale)bksl-nl taillepy-undtotale += taillebksl-nl resultat.append(souspy-undarbre)bksl-nl return resultat, taillepy-undtotalebksl-nlbksl-nl temp = [y + 1 for y in chemin] + [0]bksl-nl arbre, taille = etape(temp, 0)bksl-nl return arbrebksl-nlbksl-nl# testsbksl-nlbksl-nlassert cheminpy-undverspy-undarbre([1, -1]) == [[], []]bksl-nlbksl-nlassert cheminpy-undverspy-undarbre([2, -1, -1, 1, -1]) == [[], [], [[], []]]bksl-nlbksl-nl

A

Version itérative

On utilise ici deux piles

🐍 Script Python

def chemin_vers_arbre(chemin):
    "correspondance de Łukasiewicz"
    arbre = [[]]
    while chemin:
        sous_arbre = []
        for _ in range(1 + chemin.pop()) :
            sous_arbre.append(arbre.pop())
        arbre.append(sous_arbre)
    return arbre.pop()

On initialise arbre avec la dernière feuille [] qui vient à la fin du codage.

arbre se construit comme une pile de sous-arbres, qui sont extraits pour fabriquer un nouveau sous-arbre plus grand. À la fin arbre ne contient qu'un élément : l'arbre en question.

Z

Indice 0

On peut essayer une version itérative qui travaille avec chemin comme une pile, et avec une autre pile dans laquelle on stocke des sous-arbres... Pas évidente à imaginer...

Sinon, on peut envisager une version récursive avec les indices suivants.

Indice 1

Il sera utile de créer une fonction etape, récursive, qui prend une liste en paramètre, ainsi qu'une position de départ et renvoie la représentation de l'arbre indiqué à cette position, ainsi que la longueur utilisée dans la liste.

Par exemple

🐍 Console Python

>>> etape([3, 0, 5, 0, 2, 0, 0, 0, 0, 0, 0], 1)
([], 1)
>>> etape([3, 0, 5, 0, 2, 0, 0, 0, 0, 0, 0], 3)
([[], []], 3)
>>> etape([3, 0, 0, 2, 0, 0], 0)
([[], [], [[], []]], 6)

Indice 2

Cette fonction récursive pourra avoir le squelette

🐍 Script Python

def etape(temp, i):
    "Fonction récursive interne"
    if temp[i] == 0:
        return [], 1
    else:
        resultat = []
        taille_totale = 1
        for _ in range(temp[i]):
            sous_arbre, taille = etape(..., ...)
            taille_totale = ...
            resultat.append(...)
    return resultat, taille_totale