Discussion :

[davcha]

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

[plxpy]

Bonjour

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

pour moi, c'est râté.

C'est une notation "standard" ? Elle porte un nom ?

[davcha]

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.

[wiztricks]

C'est une notation "standard" ? Elle porte un nom ?

Bah, en considérant çà comme une notation de Newick, çà parle un peu.
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

[davcha]

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".