Génération de mots de 'a' à 'zzzzzzzz'

Version imprimable

03/05/2008, 15h48
jack_x4

Génération de mots de 'a' à 'zzzzzzzz'

ça fait trois jours que j'essaye de coder un programme qui me génère tous les mots de a à zzzzzzzz !

:evilred:
03/05/2008, 15h52
crocodilex

Citation:

Envoyé par jack_x4

ça fait trois jours que j'essaye de coder un programme qui me génère tous les mots de a à zzzzzzzz !

:evilred:

Tous les mots ou toutes les lettres de l'alphabet ?
03/05/2008, 15h56
jack_x4

et bien faut génerer de la maniere suivante :

1) lettres utilisées : a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z.
2) ensuite faut générer tout les cas possible avec des 26 lettres.

example:
a
b
c
...
z
aa
ab
...
az
ba
...
zzzzzzzz
03/05/2008, 16h25
dapounet

Intéressant comme exercice... J'ai fait comme ça : en ajoutant 1 au caractère à droite pour passer au mot suivant. À part que si ce caractère est 'z' je le remets à 'a' et c'est le caractère de gauche que j'incrémente (sauf si c'est 'z', etc.). Je fais ça en boucle jusqu'à ce le mot devienne "zzzzzzzz". Par contre ça met beaucoup de temps à calculer si j'affiche toutes les possibilités. :?
03/05/2008, 16h28
jack_x4

Oui le fait d'afficher les étapes augmente grandement le temps pour aller au but !
Mais je pense que j'ai trouvé... je test ...
03/05/2008, 17h43
Emmanuel Delahaye

Citation:

Envoyé par jack_x4

ça fait trois jours que j'essaye de coder un programme qui me génère tous les mots de a à zzzzzzzz !

Et ? Sais-tu que pour une telle génération il faut plusieurs jours de CPU tournant à 100 %, même sur une machine moderne. As-tu fait une évaluation du nombre de combinaisons possible ?

1 lettre : 26 possibilités
2 lettres : 26 + 26 x 26 = (1 + 26) x 26 = 27 x 26 = 702
3 lettres : 702 + 26 x 26 x 26 = 702 + 17576 = 18278
4 lettres : 18278 + 26 x 26 x 26 x 26 = 475254

Tu vois le genre de progression ? (factorielle ? ) Alors avec 8 lettres, laisse tomber...

A mon avis, ce que tu cherches, c'est ça :

http://delahaye.emmanuel.free.fr/dico/
04/05/2008, 13h27
jack_x4

la rapidité n'est pas mon problème, le topic ne fait pas objet d'amélioration de temps mais le moyen de générer tout ces combinaisons.
8 boucle for ! vous voyez autre chose ?

de a à z comme table de référence c'est rapide, 26^8 , 208 milliard c'est relatif,c'est pas la mere a boire.

je ne rentre pas les caracteres spéciaux grosse lettre et numéraux !
04/05/2008, 16h09
Emmanuel Delahaye

Citation:

Envoyé par jack_x4

la rapidité n'est pas mon problème, le topic ne fait pas objet d'amélioration de temps mais le moyen de générer tout ces combinaisons.
8 boucle for ! vous voyez autre chose ?

Non.

Citation:

de a à z comme table de référence c'est rapide, 26^8 , 208 milliard c'est relatif,c'est pas la mere a boire.

Sevré trop jeune ?
04/05/2008, 18h20
ram-0000

Citation:

Envoyé par jack_x4

26^8 , 208 milliard c'est relatif

Relatif d'accord mais beau morceau quand même !!

Génération : 208 milliard à raison de 10000 itérations par secondes (cela me parait énorme mais bon) = 20 millions de secondes = 231 jours (sans panne de courant ni crash de la machine ?)

Stockage : 208 milliards multiplié par 8 caractères = 1,6 Tera octets. C'est à la portée de monsieur tout le monde maintenant (moyennant un petit effort d'investissement).

Salut,

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main()
{
    char word[8+1+1] = {0};
    int length = 0, pos = 0;
    char *traveler;
 
    traveler = word;
 
    while (length < 9)
    {
        switch (*traveler)
        {
            case '\0':
                length++;
                memset(word, 'a', length);
                puts(word);
                break;
            case 'z':
                //On reva en arrière
                while (traveler--)
                {
                    if (traveler < word)
                    {
                        traveler = word + ++pos;
                        break;
                    } //else
                    if (*traveler < 'z')
                    {
                        //on augmente celui-là et reset tous les autres après
                        (*traveler) ++;
                        memset(traveler+1, 'a', length - (traveler-word) - 1);
                        traveler = word + length - 1;
                        puts(word);
                        break;
                    }
                }
                break;
            default:
                (*traveler)++;
                puts(word);
                break;
        }
    }
 
    return 0;
}

Un petit morceau de code bien opaque et peut-être pas optimisé, mais qui je crois (je l'ai pas testé en profondeur) fais ce que tu veux.

A noter, que malheureusement pour des soucis de performance il affiche pour dernier mot 'aaaaaaaaa' et non 'zzzzzzzz' (j'espère que ce mot supplémentaire par rapport au 208 milliards autres ne causera pas trop de problèmes :()

PS: A ceux qui voudraient me jeter des pierres, je précise que je suis tout à fait conscient qu'écrire ce genre de code dans la vraie vie risque de vous faire lyncher.

04/05/2008, 18h59
coyotte507

Sinon, sans afficher, j'obtiens tous les mots de 7 lettres en 41 secondes sur mon ordi portable, donc tous les mots de 8 lettres c'est faisable.
(ça fait 195 897 809 itérations par seconde)

La version avec les if->continue le fait en 38 secondes, c'est bizarre :?
04/05/2008, 19h10
ram-0000

Citation:

Envoyé par coyotte507

La version avec les if->continue le fait en 38 secondes, c'est bizarre :?

Comme quoi en ce qui concerne l'optimisation, il vaut mieux écrire un code simple et humainement compréhensible et laisser faire l'optimiseur :?

Ben les if->continue, je trouve ça moins compréhensible que le switch.

La version avec les if->continue:

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main()
{
    char word[8+1+1] = {0};
    int length = 0, pos = 0;
    char *traveler;
 
    traveler = word;
 
    while (length < 8)
    {
        if (*traveler == '\0')
        {
            length++;
            memset(word, 'a', length);
            puts(word);
            continue;
        } //else
        if (*traveler == 'z')
        {
            //On reva en arrière
            while (traveler--)
            {
                if (traveler < word)
                {
                    traveler = word + ++pos;
                    break;
                } //else
                if (*traveler < 'z')
                {
                    //on augmente celui-là et reset tous les autres après
                    (*traveler) ++;
                    memset(traveler+1, 'a', length - (traveler-word) - 1);
                    traveler = word + length - 1;
                    puts(word);
                    break;
                }
            }
            continue;
        } //else
        (*traveler)++;
        puts(word);
    }
 
    return 0;
}

05/05/2008, 09h16
Thierry Chappuis

Pour la générations de combinaisons, permutations, etc, voir les liens postés ici: http://www.developpez.net/forums/sho...43&postcount=2

Thierry

Sinon j'avais fait comme ça :

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
#include <stdio.h>
#include <string.h>
 
 
int main (void)
{
   char mot[] = "       a";
   char motFinal[sizeof mot];
   int i;
   int fin;
 
   puts (mot);
   memset (motFinal, 'z', sizeof motFinal - 1);
   motFinal[sizeof motFinal - 1] = '\0';
 
   while ( strcmp (mot, motFinal) != 0 )
   {
      fin = 0;
 
      for (i = sizeof mot - 2; i >= 0 && fin == 0; --i)
      {
         if (mot[i] == ' ')
         {
            mot[i] = 'a';
            fin = 1;
         }
         else if (mot[i] != 'z')
         {
            ++mot[i];
            fin = 1;
         }
         else
         {
            mot[i] = 'a';
         }
 
      }
   }
 
   return 0;
}