Version imprimable
Hello,
Je cherche un algorithme rapide pour transformer des arbres, en python. Peut-être existe-t-il une librairie qui fait déjà ça.
Quelques exemples de transformation pour me faire comprendre :
(m,(m,a,b),c) => (m,a,(m,b,c)
(m,(m,a,b),c) => m(k(t(c),a),v(b))
avec m,k,t,a,b,c des objets quelconques
Il est assez important que l'algo soit rapide.
Des idées ?
Merci
Bonjour
pour moi, c'est râté.Citation:
Envoyé par davcha
C'est une notation "standard" ? Elle porte un nom ?
Oui. Désolé pour le manque de précision : http://fr.wikipedia.org/wiki/S-expression
En ce qui concerne la question posée ici, il s'agit de tuples python imbriqués qui forment une structure arborescente.
La permutation des membres gauche/droite est un exemple de transformation simple : (a, b) => (b, a).
J'espère que c'est un peu plus clair.
Bah, en considérant çà comme une notation de Newick, çà parle un peu.Citation:
Envoyé par plxpy
Après, il faut décrire la transformation à effectuer...
Ce qui sera un mini-langage en soi.
De tels outils existent mais j'ai le souvenir que c'est un problème NP-hard => ca traitera certaines catégories de transformations.
Dans tous les cas, il va falloir mieux définir le besoin et se contenter de ce qu'on trouve avec Google.
- W
L'apprentissage de transformations à partir d'exemples peut être un pb NP-dur et décider si un ensemble de transformation ne comporte pas de cycles est NP-dur ou indécidable, je ne sais plus.
Ici, je me contente seulement de transformations connues d'un arbre vers un autre.
Je suis quasi certain qu'on peut faire ça avec du pattern-matching "à-la-OCaml".