Correspondance de Łukasiewicz⚓︎
Généralités
On rappelle qu'un arbre est dit :
- enraciné : s'il possède au moins un nœud ; la racine
- sans étiquette : les nœuds ne portent pas ici d'identifiant ni de valeurs
- ordonné : l'ordre de ses sous-arbres compte
Dans ce cas, un arbre peut être modélisé avec une liste Python :
- Une feuille (un nœud externe) sera représentée par une liste vide
[]
; la liste de ses sous-arbres est vide. - Un nœud interne sera représenté par la liste de ses sous-arbres donnés dans l'ordre.
- Un arbre sera donné par la représentation de sa racine.
Dans cet exercice, on ne travaille qu'avec des arbres enracinés, ordonnés, sans étiquette. On pourrait cependant aussi accepter les étiquettes.
Exemples
représenté en interne avec [[[], []], [[]], []]
représenté en interne avec [[[]], [[], []], []]
Les deux arbres ci-dessus sont différents, d'où la qualification ordonné.
représenté en interne avec [[], [[], [[], []], [], [], []], []]
Correspondance de Łukasiewicz
Pour chaque arbre, on note
1] On construit d'abord une liste nb_sous_arbres
:
- qui commence avec le nombre de sous-arbres de la racine,
- que l'on complète récursivement avec le contenu des listes
nb_sous_arbres
de chaque sous arbre. - Pour un feuille, cette liste est
[0]
; il y a sous-arbre, et donc rien à ajouter.
Exemple :
, la racine possède [3, ...a..., ...b..., ...c...]
-
Le sous-arbre
a
est une feuille, on remplace donc...a...
par0
, il y a nœud et on n'a pas de sous arbres à évoquer. -
Le sous-arbre
b
possède nœuds, on remplace donc...b...
par5, 0, ..., 0, 0, 0
; il y avait 4 feuilles, on a déjà placé les0
, reste à compléter par le dernier morceau qui possède 2 feuilles, donc2, 0, 0
-
Le sous-arbre
c
est une feuille, on remplace...c...
par0
On obtient la liste [3, 0, 5, 0, 2, 0, 0, 0, 0, 0, 0]
Propriétés :
- Cette liste est de longueur
et de somme égale à . - Cette liste se termine toujours par un
, qui représente la feuille la plus à droite de l'arbre. - La somme des
premiers termes est toujours supérieure ou égale à pour tout de à .
2] On construit une liste chemin
à partir de cette liste, en ôtant
Propriétés :
- Cette liste
chemin
est de longueur et de somme nulle. - La somme des
premiers termes est toujours positive pour tout de à .
Exemple, à partir de la liste [3, 0, 5, 0, 2, 0, 0, 0, 0, 0, 0]
, on construit
[2, -1, 4, -1, 1, -1, -1, -1, -1, -1, -1]
On obtient donc une modélisation d'un chemin de
Avec l'exemple précédent, on obtient
Réciproquement, pour tout chemin de Łukasiewicz, on pourrait reconstruire un arbre avec le procédé inverse ; c'est plus délicat à implémenter. Ce sera l'objet d'un autre exercice, plus difficile.
Écrire une fonction arbre_vers_chemin
qui implémente une partie de la correspondance de Łukasiewicz.
Exemples
représenté en interne avec [[], []]
, donne un chemin
qui correspond à la liste [1, -1]
>>> arbre_vers_chemin([[], []])
[1, -1]
représenté en interne avec [[], [], [[], []]]
, donne un chemin
qui correspond à la liste [2, -1, -1, 1, -1]
>>> arbre_vers_chemin([[], [], [[], []]])
[2, -1, -1, 1, -1]
def arbrepy-undverspy-undchemin(arbre):bksl-nl ...bksl-nlbksl-nl# testsbksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[], []]) == [1, -1]bksl-nlassert arbrepy-undverspy-undchemin([[], [], [[], []]]) == [2, -1, -1, 1, -1]bksl-nlbksl-nldef arbrepy-undverspy-undchemin(arbre):bksl-nl def etape(arbre):bksl-nl "Fonction récursive interne"bksl-nl resultat = [len(arbre)]bksl-nl for souspy-undarbre in arbre:bksl-nl resultat.extend(etape(souspy-undarbre))bksl-nl return resultatbksl-nlbksl-nl chemin = [y - 1 for y in etape(arbre)]bksl-nl chemin.pop()bksl-nl return cheminbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert arbrepy-undverspy-undchemin([[], []]) == [1, -1]bksl-nlassert arbrepy-undverspy-undchemin([[], [], [[], []]]) == [2, -1, -1, 1, -1]bksl-nlbksl-nlbksl-nl