[Algo C++] Anagrammes

Résolu/Fermé

KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 - 19 août 2009 à 20:04
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 - 20 août 2009 à 15:23

Bonjour,

Je suis en train de faire un programme qui recherche des anagrammes (j'entends par anagramme un mot qui peut s'écrire avec les lettres d'un autre). Après de nombreux essais je pensais avoir définitivement trouvé comment écrire ma fonction principale isAnagram, mais je viens de terminer le reste du code et je m'aperçois qu'en fait elle me donne des faux positifs (et peut-être des faux négatifs mais c'est moins évident à déterminer)

Si quelqu'un pouvait regarder mon code et me dire comment le corriger... Merci !

// stringD.h

class stringD
{
private:
    s1,s2:std::string;

// s1 et s2 ne contiennent que des lettres majuscules entre 'A' et 'Z'
// s2 contient les mêmes lettres que s1 mais triées dans l'ordre alphabétique

public:
    size_t size(void);
    bool isAnagram(stringD s);
};

// stringD.cpp

bool stringD::isAnagram(stringD s) // this* est-il écrit avec les lettres de s ?
{
    if (size()>s.size()) return false;

    for (unsigned i=0,j=0; j<s.size(); i++, j++)
    {
        while (s.s2[j]<s2[i])
            j++;

        if (s2[i]!=s.s2[j])
            return false;
    }
    return true;
}

Un exemple de faux positif :

x.s1="LETTRES", x.s2="EELRSTT"
y.s1="LUTTEUR", y.s2="ELRTTUU"

bool b=x.isAnagram(y); // b==true !?

A voir également:

Algorithme anagramme
Logiciel algorithme gratuit - Télécharger - Édition & Programmation
Code ascii algorithme - Guide
Algorithme excel - Forum VB / VBA
Remplir une matrice algorithme - Forum Pascal
Ecrire un algorithme qui permet de resoudre ax²+bx+c=0 - Forum Programmation

5 réponses

Réponse 1 / 5

KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
20 août 2009 à 14:20

Mon problème ne vient pas de là mais si ça peut aider, voici mon constructeur stringD :

#include <string>
#include <algorithm>

stringD::stringD(const std::string s):s1(s),s2(s) // s doit être un mot en majuscule
{
    std::sort(s2.begin(),s2.end());
}

Réponse 2 / 5

Char Snipeur Messages postés 9696 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 3 octobre 2023 1 297
20 août 2009 à 08:23

je ne comprend pas ton algorithme.
Pourtant, si tu as les lettres du mot trié alphabétiquement, il suffit de voir si les chaine s2 sont identiques.
Deux mots sont anagramme lorsqu'ils contiennent les même lettres. Et si ils contients les même lettres, leur trie alphabétique est le même.
ta fonction devrais être juste :
return s2==s.s2;

Réponse 3 / 5

KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
20 août 2009 à 13:49

Je suis d'accord sur la vraie définition d'un anagramme.
Cependant comme je l'ai dit j'entends par anagramme un mot qui peut s'écrire avec les lettres d'un autre, par exemple si je joue au Scrabble, j'ai 7 lettres et je cherche tous les mots que je puisse avoir avec ces 7 lettres.
Il y aura donc dans mes résultats d'une part des anagrammes mais aussi des mots plus courts...

Le problème c'est que mon algorithme renvoie true à des mots this* qui ne contiennent pas les lettres des s.
Ce qui me laisse encore plus perplexe, c'est que avec le même mot, si je lance plusieurs fois de suite la recherche sur le dictionnaire entier, il ne me trouve pas toujours les même faux positifs. C'est à dire qu'avec le mot "LETTRES" j'ai parfois 46 résultats positifs dans le dictionnaire, parfois 64, parfois entre les deux... Donc bien sûr les vrais "anagrammes" apparaissent toujours mais les faux positifs semblent aller et venir de façon aléatoire !

Sur l'idée mon algorithme compare des mots qui peuvent donc être de taille différente this* de taille <= à s d'où ma première ligne. Par exemple, "BON" est - selon ma définition - anagramme de "BONJOUR".
La recherche compare donc this->s2="BNO" et s.s2="BJNOORU.
Je parcours donc les deux mots en comparant les deux première lettres, ici égales -> je compare les deux deuxièmes, différentes -> j'incrémente mon "curseur" sur s.s2; pour comparer O et O, en excluant donc la lettre J.
Et je continue jusqu'à la fin, sauf si je trouve par exemple à la place du J un P, ce qui signifierait qu'il n'y ait pas de O dans s, et que this ne peut donc pas être "anagramme" de s.

Il semble que le problème vient de mon return true; final, puisque apparemment mes faux positifs sont composés de lettres de s, et uniquement de lettres supérieurs à la plus grande lettre de s !
Par exemple "LUTTEUR-ELRTTUU" est un faux positif de "LETTRES-EELRSTT" composé avec deux U supérieurs au T qui était la dernière lettre de EELRSTT...

J'arrive bien à analyser l'erreur, mais je ne vois pas comment corriger mon problème, ni même comment le traiter autrement...

Réponse 4 / 5

Char Snipeur Messages postés 9696 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 3 octobre 2023 1 297
20 août 2009 à 14:32

OK, je comprends mieux. Je n'avais pas compris ta première explication.
Comme tes lettres son ordonnées, c'est déjà plus facile.
pour que ça soit plus clair, mieux vaut découper ta boucle.

bool stringD::isAnagram(stringD s) // this* est-il écrit avec les lettres de s ?
{
    if (size()>s.size()) return false;
    int j=0;
    for (unsigned i=0; i<size(); i++)
    {
        while (s.s2[j]<s2[i])
            j++;

        if (s2[i]!=s.s2[j])
            return false;
       else j++;
    }
    return true;
}

Mais tu peux faire ça aussi en pile. (écriture en algorithme, je ne suis pas certain des fonctions utilisées)

bool stringD::isAnagram(stringD s) // this* est-il écrit avec les lettres de s ?
{
    if (size()>s.size()) return false;
    for(int i=0;i<s.size();++i)
    {
          int pos=s.s2.find(s[i]);
          if(pos==std::string::npos) return false;
          else s2.remove(pos);
    }
    return true;
}

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question

Réponse 5 / 5

KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
20 août 2009 à 15:23

Merci, ton premier algorithme ne marche pas mieux, mais en partant sur l'idée du deuxième algorithme j'ai réussi à modifier et à obtenir les bons résultats, et de plus avec cette méthode j'ai l'impression que je peux m'abstenir du tri préalable des lettres, ce qui me ferai gagner temps/mémoire lors du chargement du dictionnaire

bool stringD::isAnagram(stringD s)
{
    if (size()>s.size()) return false;    
    for(unsigned i=0;i<size();++i)
    {
        unsigned pos=s.s2.find(s2[i]);
        if(pos==std::string::npos) return false;
          else s.s2.erase(pos,1);
    }
    return true;
}

Merci encore !

Discussions similaires

algorithme résoudre ax²+bx+c=0

Générer toutes combinaisons possibles Euromillions dans Excel

Anagramme

Exercice simple d'algorithmique

algorithme qui effectue le produit des nombres

Discussions similaires

Newsletters