Discussion :

[Guesset]

Bonjour,

Bonjour, j'ai lu plusieurs fois ta proposition d'algo simple et brutal, mais je n'ai pas compris grand chose
mcd c'est la liste, vector, qui contient tous les mots du dico trié dans l'ordre alphabétique, on est d'accord.
Ensuite, acd, c'est la liste qui contient les anagrammes... Dans un premier temps, on duplique mcd dans acd si j'ai bien compris.
Après la recherche dichotomique, j'ai pas trop bien compris comment tu fais la dichotomie. Y a un truc qui m'échappe.

Les 2 listes sont identiques, l'une est triée par mot, l'autre par anagramme standard (on a donc dans cette dernière les anagrammes identiques en séquence). On peut utiliser des pointeurs pour la seconde liste mais le gain en place est payé par un coût en temps qui semble la priorité ici.
Si j'ai un mot donné, je le recherche (par dichotomie pour avoir un temps de recherche en O(log n) et non en O(n)) dans la première liste et trouve son anagramme standard qui me sert de clé pour la recherche (toujours dichotomique) dans la seconde liste. Ensuite je balaye la seconde liste au dessus et en dessous de l'élément trouvé pour collecter tous les anagrammes réels (c'est linéaire mais sur des nombre très réduits car les anagrammes sont assez peu nombreux).

Si j'ai fait le nettoyage des mots sans anagramme (ie ceux qui n'ont qu'une entrée dans la seconde liste initiale), l'échec de la première recherche (entrée trouvée != mot recherché) retourne directement l'information de l'absence d'anagramme. Ce travail complémentaire diminue la taille tout en accroissant sensiblement les performances de recherche. Dans le cas de cette solution, on inverse la séquence des tris : trier par anagramme O(n log n), supprimer les entrées avec un seul anagramme O(n) -> n' << n (pas décalage mais petit devant n ) , dupliquer (ou créer une liste de pointeurs) O(n') puis trier dans l'ordre lexicographique O(n' log n'). Ce qui ne devrait pas prendre sensiblement plus de temps que l'algorithme sans suppression d'entrées.

Salutations