TOUS LES ANAGRAMMES D'UN MOT ( COMBINATOIRE + PERMUTATION )

Information sur la source

Catégorie :Maths Classé sous : anagramme, combinatoire, permutation, combinaison, mot Niveau : Initié Date de création : 12/04/2003 Date de mise à jour : 04/12/2004 02:06:25 Vu / téléchargé: 24 027 / 672

Auteur : Alain Proviste

Site perso

Ecrire un message privé

Ce membre participe au partage de revenus publicitaires

Note :

7,75 / 10

Commentaire sur cette source (31)

Ajouter un commentaire et/ou une note

Description

Cliquez pour voir la capture en taille normale

Voici un petit programme qui renvoit dans un tableau passer by ref dans une procédure toutes les combinaisons possibles des lettres d'un mot.
Le traitement est plutôt rapide : 26 secondes sur mon Pii-300 196 Mo de ram pour traiter un mot de 7 lettres ( soit 7! = + de 5000 combinaisons ), sachant que c'est beaucoup plus rapide sans le DoEvents
Un petit exemple :

Call AnnaGramme("voie",tbl())

renverra dans le tableau tbl redimmensionner à Factorielle de 4 = 24 cases les mots suivants :
voie
voei
vioe
vieo
veoi
veio
ovie
ovei
oive
oiev
oevi
oeiv
ivoe
iveo
iove
ioev
ievo
ieov
evoi
evio
eovi
eoiv
eivo
eiov

Dans le zip un exemple d'utilisation de la procédure.

A partir de 8 lettres le programme dans le zip bug. Ca ne vient pas de ma routine mais plutôt du fait que les listbox ne peuvent pas accepter plus de 32767 entrées et qu'il y a plus de 40000 anagrammes d'un mot de 8 lettres.

Voici la procédure AnnaGramme en question : (Elle est pas longue, hein ? )

Source

Option Base 1
Private Sub AnnaGramme(mot As String, ByRef tablo() As String)
Dim longueur As Byte
Dim i As Byte
Dim l As Double
Dim k As Byte
Dim j As Double
Dim motTab() As String * 1
Dim annaTab() As String
Dim tempmot As String
Dim temptab() As String
Dim lenTab As Double
Dim pos As Double
Dim Find As Boolean
longueur = Len(mot)
If longueur = 1 Then
ReDim tablo(1)
tablo(1) = mot
Exit Sub
End If
ReDim motTab(longueur)
For i = 1 To longueur
motTab(i) = Mid(mot, i, 1)
Next i
lenTab = Fac(longueur)
ReDim annaTab(lenTab)
For i = 1 To longueur
tempmot = vbNullString
Find = False
For k = 1 To longueur
If Find Then
tempmot = tempmot & motTab(k)
Else
If motTab(k) = motTab(i) Then
Find = True
Else
tempmot = tempmot & motTab(k)
End If
End If
Next k
If Len(tempmot) = 1 Then
ReDim temptab(1)
temptab(1) = tempmot
Else
Call AnnaGramme(tempmot, temptab())
End If
For j = 1 To lenTab / longueur
For l = 1 To UBound(temptab())
annaTab(l + pos) = motTab(i) & temptab(l)
Next l
DoEvents
Next j
pos = pos + lenTab / longueur
Next i
tablo() = annaTab()
End Sub
Private Function Fac(Number As Byte) As Double
Dim i As Byte
Dim a As Double
a = 1
For i = 1 To Number
a = a * i
Next i
Fac = a
End Function

Option Base 1

Private Sub AnnaGramme(mot As String, ByRef tablo() As String)

    Dim longueur  As Byte
    Dim i         As Byte
    Dim l         As Double
    Dim k         As Byte
    Dim j         As Double
    Dim motTab()  As String * 1
    Dim annaTab() As String
    Dim tempmot   As String
    Dim temptab() As String
    Dim lenTab    As Double
    Dim pos       As Double
    Dim Find      As Boolean
   
    longueur = Len(mot)
    
    If longueur = 1 Then
        ReDim tablo(1)
        tablo(1) = mot
        Exit Sub
    End If
    
    ReDim motTab(longueur)
    
    For i = 1 To longueur
        
        motTab(i) = Mid(mot, i, 1)
        
    Next i
    
    lenTab = Fac(longueur)
    
    ReDim annaTab(lenTab)
    
    For i = 1 To longueur
        
        tempmot = vbNullString
        
        Find = False
        
        For k = 1 To longueur
            If Find Then
                tempmot = tempmot & motTab(k)
            Else
                If motTab(k) = motTab(i) Then
                    Find = True
                Else
                    tempmot = tempmot & motTab(k)
                End If
            End If
        Next k
     
        If Len(tempmot) = 1 Then
            ReDim temptab(1)
            temptab(1) = tempmot
        Else
            Call AnnaGramme(tempmot, temptab())
        End If
        
        For j = 1 To lenTab / longueur
            For l = 1 To UBound(temptab())
                annaTab(l + pos) = motTab(i) & temptab(l)
            Next l
            DoEvents
        Next j
        
        pos = pos + lenTab / longueur
        
    Next i
    
    tablo() = annaTab()

End Sub

Private Function Fac(Number As Byte) As Double

    Dim i As Byte
    Dim a As Double
    
    a = 1
    
    For i = 1 To Number
        a = a * i
    Next i
    
    Fac = a

End Function

Conclusion

Ce programme n'est pas transcendantal mais j'en suis plutôt fier et puis j'ai bien du passer une heure dessus à plancher alors si un morveux minable le reprends à son compte je le pends moi-même avec ses propres boyaux, et sans anesthésie.
J'ai essayé d'optimiser le code au maximum mais j'y connais rien en algorithmique, j'y connais pas grand chose non plus en programmation donc bon si des plus doués arrivent à améliorer le rendement, tant mieux, qu'ils me mettent au courant.
J'ai jamais eu d'erreur de dépassement de capacité ou d'éclatage de pile ou de saturation de la mémoire ou de trucs du genre chez moi.
Un truc que j'ai pas fait parce que je m'en contrefiche, c'est de supprimer les doublons ( ben oui si la même lettre reviens dans le mot alors y a un peu moins d'anagrammes parce que "maman" et "maman" c'est la même chose )
C'est pas commenté mais pour moi c'est très clair donc si qq veut une explication qu'il se manifeste il sera servi.

Et laissez des commentaires que Diantre.

Niveau 2, j'ose ?

Voir la source de Bricomix :

http://www.vbfrance.com/article.aspx?Val=8419

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Form1.frm 4 046 octets
Form1.frx778 octets
prjAnna.exe24 576 octets
prjAnna.vbp 609 octets
prjAnna.vbw 52 octets

Télécharger le zip

Historique

04 décembre 2004 02:06:25 :: orthographe

Sources du même auteur

Toutes les sources de Alain Proviste

Sources de la même categorie

Toutes les sources de la catégorie Maths

Sources en rapport avec celle ci

Commentaires

Commentaire de Ricpperso le 12/04/2003 21:34:54

pas trés interressant, car, sa melange uniquement les lettres, rien de plus, ca en forme pas des mots a partir d'autres mots.
Commentaire de Alain Proviste le 12/04/2003 21:38:25 administrateur CS

ouais je sais je l'ai marqué que ca servait à rien patate. C'est l'algo qui est interressant patate.
Commentaire de DeAtHCrAsH le 12/04/2003 22:15:54

Rien qu'une petite remarque ... Prend ton dico et regarde la definition du mot anagrame .... Un anagrame est une combinaison de lettre qui selon leur positions, forment un mot qui existe .. et non pas ce que tu as fait ... =)
Commentaire de DeAtHCrAsH le 12/04/2003 22:33:49

LoooooL ... Je critique pas ta source coco =)
Le code est peut etre bien... Mais ton titre est mal choisi ...
Commentaire de wbr le 12/04/2003 23:00:12

Ton prog il est bien je trouve, ça me servira probablement jamais mais je l'aime!

De l'art qu'on dit lol ;)
Commentaire de MPi le 13/04/2003 04:59:52

3 tableaux, 10 variables...
il me semble qu'on aurait pu faire mieux...

mais c'est un bel effort et ça donne une vitesse d'exécution quand même bonne.
Commentaire de Nestor le 13/04/2003 11:06:23

MANQUE DE COMMANTAIRES !!!!!!

2/10
Commentaire de Alain Proviste le 13/04/2003 13:43:48 administrateur CS

Nestor, s'il y a quelque chose que tu ne comprends pas dans la routine je peux te l'expliquer avec plaisir.
Je ne supporte de commenter mes sources, ça me prends un temps fou pour rien et en plus ça m'embrouille plus qu'autre chose.

De toutes façons cette source ne vaut pas 2/10
Commentaire de Nestor le 13/04/2003 16:09:27

alors 1/10 :D
Commentaire de wbr le 13/04/2003 16:12:50

Un ptit 10 ça va peut-être pouvoir réajuster la connerie de Nestor! Dites, ya que moi qui l'aime cette source?
Commentaire de DeAtHCrAsH le 13/04/2003 17:15:35

Un deuxieme petit 10 de quoi remonter tout ca ...
NESTOR> COmme on dis charité bien ordonné commence par sois meme " ... Alors avant de de poser tes commentaires bidon, montre nous ce que tu vaut =)
Commentaire de Bricomix le 13/04/2003 17:58:15

C'est très bien mais ...

Je viens d'en faire un en environ 30 minutes, beaucoup plus rapide :
- le tiens met 2.9 secondes sur mon ordi pour faire un mot de 7 lettres
- le miens met 0.06 scondes sur mon ordi pour faire un mot de 7 lettres, et 0.33 secondes pour faire un mot de 8 lettres (ce qui donne 40320 mots à la fin...)

Si vous le voulez, demander le moi en-dessous pour que je poste le mien.
Commentaire de wbr le 13/04/2003 19:24:51

Pourquoi pas
Commentaire de Alain Proviste le 13/04/2003 19:34:02 administrateur CS

je veux bien voir parce que 0.33 secondes pour 40000 mots ce serait pas mal. ( moi pour 8 lettres ça met 20 minutes sur mon 300 lol )
Commentaire de Ricpperso le 13/04/2003 19:37:12

bon, d'abors alain proviste, certe c'est un site de code, mais, faut aussi que les sujets collent avec les progs.

De plus, tu n'accepte pas les critiques, alors dehors.

Certe l'algo est bien, mais, moi je parle du prog, pas de l'algo, l'algo de plus peut être amélioré.

Autre chose, commenté n'est pas unitile mais bien, en effet, même si t'es comme moi ou d'autre, autodydacte, trés bien, mais tous le monde ne l'est pas, il y a plein de novice.

Dernière chose, sache que je ne t'es aps mis de note, car je voulais pas te rabaisser.

Sinon bonne continuation, tes autres progs sont pas mal.

aller je te mets un 7/10. ;)
Commentaire de Bricomix le 14/04/2003 10:32:28

C'est bon, la source est dispo ici : http://www.vbfrance.com/article.aspx?Val=8419

Venez la tester, et comparez la avec celle-ci SVP !
Commentaire de Seb_d_angers le 14/04/2003 11:11:32

Ricpperso > "Autre chose, commenté n'est pas unitile mais bien, en effet, même si t'es comme moi ou d'autre, autodydacte, trés bien, mais tous le monde ne l'est pas, il y a plein de novice"

Permet moi de te dire que les commentaires ne servent pas qu'aux novices... dis toi qu'il peuvent meme te servir à toi, toi qui a créer ton propre soft !!!! Bah oui, reviens sur un programme que tu as fais il y a quelques mois ou plus... c'est compliqué de savoir ce qu'on a bien pu faire à cet endroit, on se demande meme si ce code est bien de nous...
Les commentaires c'est pour les "pros", les "vrais" développeurs...
Commentaire de Bricomix le 14/04/2003 11:29:47

Ricperso > Seb_d_angers a raison ... reviens donc sur un code assez complexe que tu as écrit il y a 6 mois... Si tu l'avais commenté, je suis sur que tu aurais passé moins de temps à le comprendre
Commentaire de Ricpperso le 14/04/2003 12:06:15

j'ai cité une utilité entre autre des commentaire (excuzer moi d'avoir oublié par exemple), et je me suis amélioré dans la prog ;) (bien que j'en mets plus, car la j'ai plus du tout le tps, j'ai un prog (en c++) qui me prends tous me tps).
Commentaire de Warny le 14/04/2003 14:10:21

Alain Proviste, quelques remarque sur ton code

Sur la forme pour commencer :
- Comme d'autres ici te l'on déjà dit, il faut mettre des commentaires
- Il faut aussi que tes variables aient des noms explicites

En un coup d'oueil, je ne comprend pas comment marche ton programme, je suis obligé de l'analyser finement. Ceci lui enlève la valeur d'exemple que tu veux lui donner. Les commentaires ont donc déjà deux utilités premières : comprendre ton code et partager ton code.
En plus Les commentaires te permettent de voir que tu fais des programmes pas optimisés (je ne parle pas que pour toi ;) ). En effet, lorsque tu écris ton commentaire, 90% du temps tu te rend compte qu'il y a plus simple, les 10% restant n'arrivant... qu'au bout d'un ou deux essais voire peut-être plus.

Sur le fond :
- Plutôt que de te pourrir la vie avec des listes, fait une procédure de sortie dans laquelle tu indiques toutes les démarches à suivre pour enregistrer tes anagrammes (par exemple les écrire dans un fichier :) ). ceci permet de te concentrer sur l'algorithme lui-même
- lorsque tu calcules l'anagramme d'un mot avec plusieurs lettre identiques, ça génère plusieurs anagrammes identiques, il faut donc que tu prennes en compte l'élimination de ces anagrammes (il y a plusieurs méthodes)
- L'affichage prend toujours énormement de temps il ne faut donc pas toujours metre à jour les éléments graphique et la liste en est un (et oui windows est et reste un os graphique). Ne fait donc pas les doevents à chaque boucle, ajuste les au 1/12 ou 1/24 de seconde d'execution.

Pour la petite indiquation, ta définition d'anagramme est bonne.
Commentaire de Alain Proviste le 14/04/2003 18:49:03 administrateur CS

Warny lis les sources avant de mettre de commentaires. L'affichage dans la liste ne se fait qu'après que tous les anagrammes aient été trouvés et j'ai bien précisé que je moquais des doublons.
Commentaire de Kaisermann le 14/04/2003 19:41:18

Tu t'es fait devancé sur ce coup là Alain P, Bricomix a tout niqué !
Commentaire de Bricomix le 14/04/2003 19:52:10

J'ai updaté ma source maintenant pour 9 lettres sur le miens ca met 1 seconde.
Commentaire de Ricpperso le 14/04/2003 20:18:16

dis, Alain, pour savoir si le mot existe, tu prends un fichiers texte, et tu regarde si le mot est dans le fichier, tu veux un dico, prend celui de Word XP ou d'un autre traitement de texte, ou encore il y a plein de super dico. Le code est trés simple, suffit de faire une boucle.

Seul hic, ca risque d'être un peu long.
Commentaire de Ricpperso le 14/04/2003 20:18:31

un peu long => l'éxécution.
Commentaire de Alain Proviste le 14/04/2003 20:28:38 administrateur CS

Oui ricpperso, j'y avais pensé mais ce n'était pas mon but de trouver les ana existants.
Commentaire de Bricomix le 14/04/2003 20:36:18

Ricpperso > pour un jeu j'avais fais un algo pour ca. Plutot que de chercher a chaquae fois si le mot existe, autant prendre chaque mot et verifier qu'il y a les bonnes lettres ! Moi ca prenait 5 secondes (sur mon XP1900+) pour un fichier texte avec + de 60000 mots
Commentaire de Ricpperso le 15/04/2003 13:27:52

oui, c'est mieux.
Commentaire de Florent le 22/04/2003 16:46:27

Faut espérer qui ait un amateur des chiffres et des lettres qui tombe sur cette page...
CONSONNE
Commentaire de fredoche4 le 14/11/2004 16:45:55

salut Alain ,
c pas mal continue ton tonton de jacou
Commentaire de kalif le 01/02/2007 15:55:10

bravo, c'est exactement ce que je cherchais lol ( :o je parie que tu avais deviné )