Aller au contenu

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])
[[], [], [[], []]]
###
# 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 ∞/∞

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-nlNone

A

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 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_rec([3, 0, 5, 0, 2, 0, 0, 0, 0, 0, 0], 1)
([], 1)
>>> etape_rec([3, 0, 5, 0, 2, 0, 0, 0, 0, 0, 0], 3)
([[], []], 3)
>>> etape_rec([3, 0, 0, 2, 0, 0], 0)
([[], [], [[], []]], 6)
Indice 2

Cette fonction récursive pourra avoir le squelette

🐍 Script Python
def etape_rec(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_rec(..., ...)
            taille_totale = ...
            resultat.append(...)
    return resultat, taille_totale
Retour en haut de la page