Réponse à #25 :

C'est une jolie façon de présenter les choses. Ça explique encore le lien avec les nombres de Catalan : https://fr.wikipedia.org/wiki/Nombre_de … es_entiers

Sinon, mon programme a donné que les 4 mots de 7 lettres dont on parlait plus haut sont :
* bacabac = a + babcba = acbcac + a
* bcbabcb = a + acbcac = abac + cac
* cabacab = bc + cbabc = bcacb + bc
* cbcacbc = babcba + a = bab + baca

On remarque que la 4e ligne est l'antisymétrique de la 2e, et que la 1e et la 3e sont auto-antisymétriques.

Pour ces 4 mots en doublon, je ne retrouve qu'un seul arbre correspondant. C'est à dire que si on raisonne "forme d'arbre" ce ne sont pas des doublons.

Réponse à #26 : joli algorithme, je n'avais pas du tout pensé à ce moyen de limiter la complexité de l'analyse rétrograde.

Tu as une réponse, mais as-tu la réponse, c'est-à-dire as tu une méthode donnant la suite la plus courte ?

Ce n'est pas dur de trouver une suite convenable dans le dico, mais pour ce qui est de la plus courte, ce n'est peut-être pas aussi évident ?

OK, je vais regarder quand j'aurai un moment (sans doute pas avant quelques jours).

Tu as au fond entrepris la même approche que la mienne, à savoir traiter les lettres dans l'ordre où elles se présentent. Ce n'est pas sûr que ce soit l'approche la meilleure, un contre exemple est à trouver.....

Pour ma part, j'avais repris la théorie des arbres déjà décrite. Si elle est plus sobre en écriture ( 2n -2 lettres à écrire pour n lettres du mot final ) elle demande du temps pour bien la comprendre.

-----------------------------------------------------------------------------------------

Compléter une suite de lettres par la suite la plus courte possible pour obtenir un mot du dico.

On ne peut pas garantir avec la méthode suivante qu'on obtient toujours le complément le plus court. Toutefois, on obtient facilement une solution.

On établit un arbre avec la suite à l'aide du chemin orienté et on complète les branches manquantes ( toujours des branches droites ) des V.
Pour compacter la présentation de l'arbre (les V de bas en haut, quoique très visuels, ne sont pas tjs faciles à dessiner) on peut procéder comme ci-après sur la base d'un exemple.

Soit la suite aabcb.
 
On rappelle que le chemin orienté est la suite de lettres bc abc abc....qu'on rencontre en longeant toutes les branches de l'arbre.

On démarre donc le chemin jusqu'à obtention de la 1ère lettre de la suite, soit ici " a ".

bcaI

Pour marquer la lettre atteinte, on la complète par I. Après une lettre atteinte, la suite se complète sur la seconde ligne (il n'y a que 2 lignes ), à partir de la dernière lettre atteinte, mais pour une seule lettre, les suivantes remontent en 1ère ligne (en fait la 1ère ligne représente les branches gauches de l'arbre, la seconde les branches droites). 

bcaIcaI
....b

La lettre suivante est b, elle est sous le dernier "a".
bcaIcaI
....b..bI

Lorsqu'une lettre de la 2ème ligne est marquée, alors la 1ère lettre de la suite est en seconde ligne, à partir du 1er vide en partant de la droite, c'est à dire ici sous " c ", les lettres suivantes sont écrites en 1ère ligne à droite. Il faut s'arranger pour qu'à la fin d'un marquage, il reste au moins 1 vide en 2ème ligne. Pour cela, on peut être amené à ne pas marquer une lettre normalement prévue, mais en ajouter 3 lettre supplémentaires et marquer la dernière lettre écrite.

bcaIcaIbcI
....babI

Il ne nous manque plus que le "b"

bcaIcaIbcIbI
....babI..a

Comme tous les V de l'arbre d'un mot du dico ont 2 branches, il n'y a plus qu'à compléter les lettres de la 2ème ligne.

bcaIcaIbcIbI
cab.abIca.c.

Les lettres ajoutées si lisent sur l'arbre de droite à gauche : ccac. La suite aabcb ccac est un mot du dico.

On peut le vérifier par l'arbre, les fusions se font par paire, de droite à gauche ( paires à identifier dans le mot).

Oui, ce contre-exemple est bien vu. Je dois admettre que j'ai fini par décrocher de ce problème de a, b et c. C'est tellement vaste...

Juste pour info, les invariants qui permettent de séparer tous les mots basés sur a, b, c en 8 familles contenant respectivement :

* a
* b
* c
* aa
* cb
* ba
* ac
* cba

Il y a donc d'abord les parités des nombres de a, b ou c. Par exemple, la famille contenant "a" ne contient que des mots dont les trois parités sont IPP ou PII. Ceci permet déjà de séparer les mots en quatre, mais pas de séparer la famille de "a" de celle de "cb", ni "b" et "ac", ni "c" et "ba", ni "aa" et "cba".

Pour les séparer, il faut avoir recours à un autre invariant, puis difficile à voir : la "signature" du mot, à savoir la parité du nombre d'inversions dans le mot. Par exemple, le mot babca contient 3 inversions : babca, babca et babca, une inversion étant donc un couple de lettres dont la première dans le mot est la dernière dans l'alphabet. La signature de babca est donc impaire.

On démontre alors que dans la famille contenant "a", la signature des mots est, si les mots contiennent 1, 2, 3,... lettres, P, P, I, I, P, P, I, I... tandis que dans la famille contenant "cb", c'est la signature opposée. De même, la signature permet de séparer les 3 autres couples de familles.

Non, ce n'est pas costaud du tout. La première partie tout du moins.

Prends des mots issus de "a", par exemple, bc, cac, caab...
* pour "a", le nombre de lettres de type "a", "b", "c" est 1,0,0 soit IPP (Impair Pair Pair).
* pour "bc", c'est 0,1,1 soit PII.
* pour "cac", c'est 1,0,2 soit IPP.
* pour "caab", c'est 2,1,1 soit PII.

Il est immédiat par récurrence que les mots issus de "a" avec un nombre impair de lettres sont du type IPP, et que ceux avec un nombre pair de lettres sont du type PII.

On peut dire la même chose des mots issus de "cb", mais pas des 6 autres familles. Par exemple, les mots issus de "b" alternent entre PIP et IPI.

Par contre, l'histoire avec la signature s'observe bien sur des exemples, mais est un peu plus casse pieds à démontrer.

Oui, je crois que je ne le ferai pas, vu le temps dont je dispose en ce moment. Et me connaissant, dans deux mois je serai passé à autre chose et je n'aurai pas le courage de m'y remettre.

Pour la signature, le raisonnement est ainsi.

Imaginons qu'un mot est du type (début)a(fin), et qu'on transforme le "a" en "bc". Par exemple,  le mot (bc)a(baac) devient (bc)bc(baac).

Dans le mot initial, avant le "a", il y avait :
* un certain nombre de "a", qui ne créaient aucune inversion avec le "a", et qui n'en créeront pas non plus avec "bc".
* un certain nombre de "b", qui créaient des inversions avec le "a", mais ces inversions disparaitront avec le "bc".
* un certain nombre de "c", qui créaient des inversions avec le "a", et il y aura autant d'inversions dans le nouveau mot avec le "b".
Donc au total, il y a autant d'inversions qui disparaissent qu'il y avait de "b" avant la lettre qu'on développe.

Dans le mot initial, après le "a", il y avait :
* un certain nombre de "a", qui ne créaient aucune inversion avec le "a", et qui en créeront 2 chacun avec "bc".
* un certain nombre de "b", qui ne créaient aucune inversion avec le "a", mais en créeront 1 chacun avec "bc".
* un certain nombre de "c", qui ne créaient aucune inversion avec le "a", et qui n'en créeront pas non plus avec "bc".
Le premier point n'a pas d'influence sur la signature, car 2 est pair. Seul le nombre de "b" est à considérer.

Donc en regroupant les deux parties du mot, il suffit de considérer le nombre de "b" du mot initial. Si ce nombre de "b" est pair, alors la signature ne change pas, s'il est impair, alors la signature change.

Après relecture de ton dernier message, cette phrase :

* un certain nombre de "c", qui créaient des inversions avec le "a", et il y aura autant d'inversions dans le nouveau mot avec le "b".

n'est pas tout à fait correcte, car pas d'inversion "c" avec "a".

OK, j'ai bien fait de poser la question, je ne l'avais pas compris comme ça.

Subtil.