Détection d'anagrammes

Version imprimable

Bonjour,

je suis sur un algorithme d'anagrammes et j'essaie de l'implementer en java

je sais c'est le plus beau des langages pour faire des exercices d'algorithme mais bon c'est mon choix..

je fais donc appel a vous pour me guider dans mon parcours,

je fait un code fonctionnel mais pas évolutifs du tout.. je pense ?

j'espère que le code ne fait pas mal au yeux :X

je suis determiner a arriver a une meilleur solution avec votre aide,

le but de ce code est de detecter les possible anagrammes dans une chaine de caractère,

les chaines seul ne sont donc pas pris en compte vue leur unicité,

je fait les comparaison sur deux chaine et plus.. et fait le compte du nombre d'anagrammes,

voici le code de ma classe ou j'ai toute mes méthodes implémenter pour faire cette opération:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
public class AnagrammesImpl {
 
    //je remplie une liste avec chaque mot de la chaine de caractères
    public List<String> anagrammesMethode(String s)
    {
        List<String> mList = new ArrayList<String>();
        String  val= "";
        for (int i=0;i< s.length();i++)
        {
            val = val + s.charAt(i);
            if (s.charAt(i) == ' ' )
            {
                mList.add(val);
                val = "";
            }
        }
        return mList;
    }
 
    //je supprime les mots unique dans la liste
    public void suppressionElementUnique(List list)
    {
        for(int i=0;i<list.size();i++)
        {
            for (int j=i+1;j<list.size();j++)
                if(list.get(i).equals(list.get(j)))
                {
                    list.removeAll(Arrays.asList(list.get(j)));
                }
        }
    }
 
    //je trie les mots par ordre alphabetique et trie chaque mot charactères par charactères
    public void trieListeEtMot(List<String> list,List listeTrier)
    {
 
        Collections.sort(list);
        for(int i=0;i<list.size();i++)
        {
            char[] c = list.get(i).trim().toCharArray();
            Arrays.sort(c);
            String sorted = new String(c);
            listeTrier.add(sorted);
        }
    }
 
    //je creer un liste et ajoute les anagrammes dans la liste
    public ArrayList listeAnagrammesChaineChar(List<String> list)
    {
        Collections.sort(list);
        ArrayList listeAnagrammes = new ArrayList() ;// int i=0;
        for(int i=0;i<list.size();i++)
        {
            for(int j=i+1;j<list.size();j++)
            {
                if(list.get(i).equals(list.get(j)))
                {
                    listeAnagrammes.add(list.get(i));
                }
            }
 
        }
        return listeAnagrammes;
    }
    //je supprime les doublon dans les anagrammes et fait le compte de mot
    public int suppressionDoublonAnagrammeEtCalcluNbAnagramme(List list)
    {
        int cpt=0;
        Set set = new HashSet() ;
        set.addAll(list) ;
        ArrayList distinctList = new ArrayList(set);
        for(int i = 0;i<distinctList.size();i++)
        {
            cpt++;
        }
        return cpt;
    }
}

le main est deja implémenter comme je disait le tous est fonctionnel.. ;)

mais il ne faut pas que cela soit fonctionnel pour être évolutifs etc...

Merci d'avance pour vos réactions.

15/09/2016, 10h25
CliffeCSTL

On aime pas le code ici, pourquoi ne pas poster ton algo ?

Préférence pour pseudo code

Merci pour ta réaction.

Je voudrait améliorer mon code..

Donc a mon sens j'ai poster le code plutôt que le pseudo code.

donc mon a ta demande le pseudo code:

merci pour vos réactions.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
Fonction anagrammesMethode(chaineDeCaractères)
	nouvelle listeDeMots
	for i de 1 jusqu'a taille de chaineDeCaractères faire
		valeur => valeur + charactère de i
		if charactère de i est égale à " "
			ajouter valeur à listeDeMots
			mettre valeur a zero
		fin 
	fin 
fin
 
Function suppressionElementUnique(listeDeMots)
	for i de 1 jusqu'a taille de listeDeMots faire
		for j de i+1 jusqu'a taille de listeDeMots faire
			if listeDeMots de i est égal listeDeMots de j
				supprimer tous les elements de listeDeMots de i
			fin 
		fin 
	fin 
fin
 
Fonction trieListeEtMot(listeDeMots)
	nouvelle listTrier
	for i de 1 jusqu'a taille => listeDeMots faire
		trie charactère de listeDeMots de i
		ajouter listeDeMots de i dans listTrier
	fin 		
fin
 
Fonction listeAnagrammesChaineChar(listTrier)
	trie listTrier
	nouvelle listeAnagrammes
	for i de 1 à taille de listTrier faire
		for j de i+1 jusqu'a taille de listTrier faire
			if listTrier de i est égale a listTrier de j
				ajout listTrier de i à listeAnagrammes
			fin 
		fin 
	fin 
fin
 
Function suppressionDoublonAnagrammeEtCalcluNbAnagramme(listeAnagrammes)
	suppression doublon de listeAnagrammes
	retour taille listeAnagrammes
fin

Trop compliqué ton pseudo code, ça donne pas envie de le lire :D (for, for, if, if ...)
Code:

1 2 3 4 Soit une chaîne de caractères S de taille N; Pour n = 2 à N - 1 faire Pour chaque couple (s1, s2) de sous chaînes de S, tel que s1 != s2 et (s1, s2) contiennent n éléments faire Tester anagramme (s1, s2);
Sinon pour le code java, je pense qu'il vaut mieux aller dans le bon forum.

15/09/2016, 17h08
sinzen

Merci pour ta réaction

OK bien compris,

Je vais essayer sur le forum adéquat.

Merci encore.
19/09/2016, 13h47
Flodelarab
Bonjour :coucou:

Pour identifier un anagramme, on ne recherche pas les lettres de l'un dans l'autre.
On calcule la signature des mots, et si les signatures sont identiques ils sont anagrammes l'un de l'autre.

Une signature est à choisir. On peut par exemple trier les lettres du mot.

Un exemple possible:
Code:

1 2 3 mot -> signature gare -> aegr rage -> aegr
"gare" est donc un anagramme de "rage".