Discussion :

[leputois]

Bonjour, alors je vous explique vite fait:

Je dois réaliser en c un programme qui prend un tableau composé de mots.
Je doit ensuite trouver dans ce tableau tous les anagrammes.

ex: [car, marion, test, manoir, rac] en entrée, et je doit afficher :

car rac
marion manoir
test

Il faut que mon programme soit le plus rapide possible, donc j'ai pensé à affecter une valeur à chaque lettre (nombre premiers), ensuite multiplier les valeurs entre elles afin que deux anagrammes aient le même nombre. (si C =3, A = 5, R=7; car 3*5*7 == 7*5*3 rac)

ensuite trier le tableau en fonction de ces nombre et ensuite afficher.

Est-ce optimal ? les nombres risquent de pas etre trop grand ?(101^25)

Merci de votre aide

[souviron34]

, donc j'ai pensé à affecter une valeur à chaque lettre (nombre premiers),

Pourquoi ça ?

les lettres ont une valeur elles-même : il n'y en a que 26..

une lettre est directement équivalent à un entier (qui plus est sur 5 bits)

'a' = 65
'b' = 66
...

donc

'a' = 1
'b' = 2
...

[leputois]

Merci de ta réponse,

Peut-être je m'y prend mal, mais j'y avais déjà pensé.

par exemple le mot "bcd" aura la valeur 2*3*4 = 24, et le mot "ch" aurra aussi la même valeur (8*3).

[anacharsis]

salut !

c'est un peu grand !
l'idée d'un tri me semble bonne : il suffit d'écrire une fonction de comparaison de 2 chaînes A et B utilisant une fonction, k, de classement des caractères dans une chaîne X (dans l'ordre alpha par exemple) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
k: X -----> k(X)
k: manoir -----> aimnor
   marion -----> aimnor           
 
comparaison: (A, B) ---------------->
si strlen(A) < strlen(B)              -1
sinon si strlen(A) > strlen(B)        +1
sinon                                 strcmp(k(A), k(B))

j'ai testé ça sur un jeux "le compte est bon" avec un dictionnaire très très gros est une rapidité satisfaisante. [qsort() pour le tri du tableau et un tri par extraction pour la fonction k()]

A+

[diogene]

...j'ai pensé à affecter une valeur à chaque lettre (nombre premiers), ensuite multiplier les valeurs entre elles afin que deux anagrammes aient le même nombre. (si C =3, A = 5, R=7; car 3*5*7 == 7*5*3 rac)

ensuite trier le tableau en fonction de ces nombre et ensuite afficher.

Est-ce optimal ? les nombres risquent de pas etre trop grand ?(101^25)

Merci de votre aide

C'est une bonne idée (mais il faut aussi garder un lien connectant le nombre obtenu avec la chaine de caractères codée pour la retrouver facilement).

La réalisation est conditionnée effectivement par la taille maximale du nombre obtenu qui dépend du nombre maximum (25 ?) de lettres d'un mot (et corrélativement si ce mot peut être une combinaison quelconque de lettres ou un mot existant dans une langue donnée).
Si on peut avoir 25 caractères quelconques, le nombre peut dépasser 10^50 (167 bits) et il faudra se tourner vers des bibliothèques multiprécision avec une perte de performance que je ne sais pas chiffrer a priori.

[souviron34]

C'est une bonne idée (mais il faut aussi garder un lien connectant le nombre obtenu avec la chaine de caractères codée pour la retrouver facilement).

La réalisation est conditionnée effectivement par la taille maximale du nombre obtenu qui dépend du nombre maximum (25 ?) de lettres d'un mot (et corrélativement si ce mot peut être une combinaison quelconque de lettres ou un mot existant dans une langue donnée).
Si on peut avoir 25 caractères quelconques, le nombre peut dépasser 10^50 (167 bits) et il faudra se tourner vers des bibliothèques multiprécision avec une perte de performance que je ne sais pas chiffrer a priori.

euh...

pourquoi ne pas stocker la multiplication en double, sans plus ?

Quant au lien, il suffit de faire un tableau qui stocke le résultat de la multilication, (et dont l'indice est donc le numéro de la chaîne) et un tableau d'entier stockant l'indice, qui, lui, sera trié..

[diogene]

pourquoi ne pas stocker la multiplication en double, sans plus ?

Pas assez précis et les long double aussi.

[kwariz]

Bonjour, alors je vous explique vite fait:

Je dois réaliser en c un programme qui prend un tableau composé de mots.
Je doit ensuite trouver dans ce tableau tous les anagrammes.

ex: [car, marion, test, manoir, rac] en entrée, et je doit afficher :

car rac
marion manoir
test

Il faut que mon programme soit le plus rapide possible, donc j'ai pensé à affecter une valeur à chaque lettre (nombre premiers), ensuite multiplier les valeurs entre elles afin que deux anagrammes aient le même nombre. (si C =3, A = 5, R=7; car 3*5*7 == 7*5*3 rac)

ensuite trier le tableau en fonction de ces nombre et ensuite afficher.

Est-ce optimal ? les nombres risquent de pas etre trop grand ?(101^25)

Merci de votre aide

Hello,

comme je suppose qu'il s'agit d'un exercice tout droit sorti d'un cours voire d'un site de concours (?) je pense que la solution la plus simple est celle que anacharsis t'a soumise.

Utiliser une fonction de hachage type p_i^o_i avec p_i le ième nombre premier et o_i le nombre d'occurence du ième caractère est peu rentable (pour cet exercice), autant rester simple.

Tu lis ton entrée, et tu stockes chaque string lues dans un tableau de struct du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
struct {
  char* orig;
  char* sorted;
  char displayed;
};

La string lue est dans orig, la string triée dans sorted et tu initialises displayed à 0.

Ensuite

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
pour chaque élément e du tableau
  si e.displayed est faux
    tu mets e.displayed à vrai
    tu affiches e.orig
    pour chaque élément e' de la suite du tableau
        si e'.displayed=faux et e.sorted=e'.sorted alors
          e'.displayed = vrai
          affiche e'.orig
    on va à la ligne

Un test alternatif consiste à créer un autre tableau de longueur la taille de ton alphabet et qui compte le nombre d'occurences de chaque caractère.

[aslo92]

Bonjour,

La solution d'anarcharsis me paraît très bonne.
Je me demande si l'utilisation d'un codage de Huffman sur tous les résultats K(x) n'améliorerait pas la vitesse du tri.

On aurait ainsi à comparer des nombres au lieu des lettres et le nombre d'octets à tester serait inférieur.

De plus le nombre de bits obtenus par un codage de Huffman sur une chaine de caractère sera variable, ce qui permet de limiter le tri.

Ex si la chaine de caractères à rechercher s'encode avec 50 bits, il suffira de tester uniquement les mots du dictionnaire qui sont également codés sur 50 bits, ce qui diminuera nettement le nombre d'éléments à trier.

[Trap D]

Dans une vie précédente, pour une appli minitel puis internet, je me souviens avoir utilisé la méthode suivante :
longueur du mot codée sur 8 bits, nombre de lettres identiques de chaque mot codé sur 4 bits, ces nombres étant rangés sur 13 octets en fonction de la lettre correspondante.
J'avais codé tous les mots possibles du dictionnaire, rangés toutes les chaines de codage dans un fichier indexé, et je retrouvais presque instantanément les anagrammes. Ça fonctionne très bien.
Ça peut surement être adapté au problème, maintenant, est-ce le plus rapide ...

[anacharsis]

le critère de rapidité ne peut intervenir qu'avec un nombre important de mots.
le lexique des flexions des mots français (Dicollecte v4.3) contient "seulement" 530000 mots.
il ne me semble pas très important de chercher le meilleur encodage pour trier le tableau qui en résulte. (sur un ordinateur individuel ; pour l'embarquer, c'est une autre paire de manches).
il est vrai que dans mon projet le tri est fait une fois pour toutes et que les mots de plus de 10 lettres sont rejetés.

A+

[souviron34]

Dans une vie précédente, pour une appli minitel puis internet, je me souviens avoir utilisé la méthode suivante :
longueur du mot codée sur 8 bits, nombre de lettres identiques de chaque mot codé sur 4 bits, ces nombres étant rangés sur 13 octets en fonction de la lettre correspondante.
J'avais codé tous les mots possibles du dictionnaire, rangés toutes les chaines de codage dans un fichier indexé, et je retrouvais presque instantanément les anagrammes. Ça fonctionne très bien.
Ça peut surement être adapté au problème, maintenant, est-ce le plus rapide ...

ça me fait penser à un truc , inspiré de ça, mais encore plus clair..

Primo, on n'a besoin de retenir que les mots de même longueur, de longueur >= 3.

D'autre part la première et dernière lettre doivent être identiques.

On fait donc une liste de mots (ou un tableau de chaînes) rangées par longueur, en éliminant tous ceux dont la première lettre est différente de la première, ou dont la longueur est > 3.

Il suffit ensuite de parcourir chaque liste par longueur en vérifiant i+1, N-i, et flagger (ou faire une sous-liste)ceux qui marchent, ou éliminer ceux qui ne marchent pas..

Non ?