Enumération des mots d'un automate

**Dark-Seal** · 12/12/2006, 15h28

Bonjour à tous

Alors voilà mon problème : à terme, mon algorithme devra énuméré toutes les combinaisons possibles (de longueur 1 à n) d'un mot. Par exemple pour le mot "MOT" je devrais trouver {"M", "O", "T", "MO", "MT", "OT", "MOT"}

J'ai essayé d'aborder le problème en trouvant un algo qui énumère toutes les possibilités de longueur n, ce qui se résumerait à n boucles imbriquées. Par exemple :

Code :

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

1
2
3
4
5
6
7
for(i=0;i<2;i++){
   for(j=0;j<2;j++){
      for(k=0;k<2;k++){
         printf("%d%d%d",i,j,k);
      }
   }
}

Ici j'énumère toutes les combinaisons de 0 et 1 de longueur 3 : {"000","001","010","011","100","101","110","111"}.
Le problème étant que je ne sais pas à l'avance combien de boucles il va me falloir et je n'arrive pas à le transformer en forme récursive (l'affichage me pose problème).
Je ne sais même pas si je m'y prend de la bonne manière car là ma complexité va être de l'ordre de O(nombre de possibilité pour une lettre)^n
En fait c'est un automate et il faut que j'affiche tous les mots représentables.

Merci

**Nemerle** · 12/12/2006, 16h24

Envoyé par Dark-Seal

Bonjour à tous

Alors voilà mon problème : à terme, mon algorithme devra énuméré toutes les combinaisons possibles (de longueur 1 à n) d'un mot. Par exemple pour le mot "MOT" je devrais trouver {"M", "O", "T", "MO", "MT", "OM", "MOT"}

t'as oublié OT,TO et TM.

Envoyé par Dark-Seal

J'ai essayé d'aborder le problème en trouvant un algo qui énumère toutes les possibilités de longueur n, ce qui se résumerait à n boucles imbriquées. Par exemple :

Code :

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

1
2
3
4
5
6
7
for(i=0;i<2;i++){
   for(j=0;j<2;j++){
      for(k=0;k<2;k++){
         printf("%d%d%d",i,j,k);
      }
   }
}

Ici j'énumère toutes les combinaisons de 0 et 1 de longueur 3 : {"000","001","010","011","100","101","110","111"}.
Le problème étant que je ne sais pas à l'avance combien de boucles il va me falloir et je n'arrive pas à le transformer en forme récursive (l'affichage me pose problème).
Je ne sais même pas si je m'y prend de la bonne manière car là ma complexité va être de l'ordre de O(nombre de possibilité pour une lettre)^n
En fait c'est un automate et il faut que j'affiche tous les mots représentables.

Merci

prend une table i[26] pour stocker des variablesde "boucles". A partir de ton code si dessus, i[0]=i, i[1]=j, i[2]=k...

et utilise une variable l qui parcourt la longueur des mots que tu veux produire (de 1 à la longueur L de ton mot initial), ainsi qu'une variable pointeuse k.

utilise un tant que l<=L. Soit, en note M[0]....M[L-1] les lettres de ton mot initial

Code :

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

1
2
3
4
5
6
7
8
9
l=-1
i[0]=L
tant que l<L
   si i[0]=L alors
      l=l+1
      k=l
      pour j de 0 à l {i[j]=j}
   finsi
...

à toi de finir!!

**Dark-Seal** · 12/12/2006, 17h24

Envoyé par Nemerle

t'as oublié OT,TO et TM.

Mince j'ai vraiment du mal, en fait l'ordre importe, je voulais mettre OT au lieu de OM (qui ne doit pas exister)

Je vais réfléchir sur ton code.
Merci

**Graffito** · 12/12/2006, 17h49

Bonjour,

Autre solution que celle proposée par Nemerle qui est d'ailleurs très bien, l'exercice se préte bien à l'utilisation d'une procedure récursive du style :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
procedure CompleteListe(Liste,debutListe,finListe,Longueur_mot) 
begin
for i=debutListe to finListe do 
     for j:=1 to longueur_mot+1 do 
          Liste.add(debutmot(liste[i],j)+Lettres[longueur_mot+1]+
                            finmot(liste[i],j) ;
if longueur_mot<Lettres.count 
   then Completeliste(Liste,finliste+1,Liste.count-1,Longueur_mot+1) ;
end ;
// Au départ,on fera :
Liste.clear ; 
liste.add(Lettres[1]) ;
if Lettres.count>1 then CompleteListe(Liste,0,0,Longueur_mot) ;

Reste à éliminer les doublons si 2 lettres sont identques

**méphistopheles** · 12/12/2006, 18h46

oui, mais la pile risque de vite saturer ...
ça doit être possible de le faire de manière itérative non ?

**Dark-Seal** · 12/12/2006, 21h25

Envoyé par Nemerle

Code :

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

1
2
3
4
5
6
7
8
9
l=-1
i[0]=L
tant que l<L
   si i[0]=L alors
      l=l+1
      k=l
      pour j de 0 à l {i[j]=j}
   finsi
...

Bon j'ai regardé ton code Nemerle, et j'aurais besoin de quelques éclaircissements si possible ^^

Code :

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

i[j]=j

Je ne comprend pas le but cette affectation, cela ne va pas effacer les i[] précédents ?

Je ne vois pas à quoi sert le k aussi.
Et l'algo que tu présentes ne fait pas L boucles à la suite ? Enfin si on l'applique à mon exemple ça ne fera pas :
char1 : 01
char2 : 01
char3 : 01 ?

Sinon Graffito j'ai encore plus de mal à comprendre ton algo

c'est du découpage de mot qu'on transmet à la boucle suivante ?

Sinon moi j'avais terminé sur ça (mais ça ne fonctionne pas) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void tous_mots(Etat *aut, char *mot, int n){
   int j;
   char *mot_temp = (char*)malloc(sizeof(char)*MAXLETTRE);
   strcpy(mot_temp,mot);
   if(n>0){
      for(j=0;j<aut->nb_transition;j++){
         if(!strlen(mot_temp))
            sprintf(mot_temp,"%c",aut->trans_suiv[j].lettre);
         else
            sprintf(mot_temp,"%s%c",mot_temp,aut->trans_suiv[j].lettre);
         tous_mots(aut->trans_suiv[j].etat_suiv, mot_temp, n-1);
         if(aut->trans_suiv[j].etat_suiv->estTerminal){
            printf("%s\n",mot_temp);
         }
      }
   }
   free(mot_temp);
}

Bon c'est avec l'automate que j'ai implanté donc je ne sais pas si vous comprendrez

De plus je crois que c'est méga lourd niveau perf.

**Graffito** · 12/12/2006, 21h37

c'est du découpage de mot qu'on transmet à la boucle suivante ?

en fait, on prend tous les mots composés avec les N premières lettres possibles et, pour chacune de ces mots, on insère la N+1 ième lettre dans toutes les positions possibles (attention, il faut éviter de composer ou d''ajouter les mots avec un blanc au milieu).

**Dark-Seal** · 12/12/2006, 22h08

Envoyé par Graffito

en fait, on prend tous les mots composés avec les N premières lettres possibles et, pour chacune de ces mots, on insère la N+1 ième lettre dans toutes les positions possibles (attention, il faut éviter de composer ou d''ajouter les mots avec un blanc au milieu).

Ah d'accord, mais en fait ce que je dois faire est plus simple, la N+1è lettre ne peut être qu'à la place N+1. Par exemple si je dois composer des sous mots de longueur 4 du mot "automate" et avec comme 1ère lettre 'm' je ne peux qu'avoir le mot "mate".
Donc si je prend 'u' en position 1 mes possibilités de lettres en position 2 : "tomae"
Si ensuite je prend 'm' il me reste "ate" etc...

Mais je sais les lettres qu'il me reste. Avec l'exemple du mot "automate" je saurais le faire de façon itérative pour une longueur donnée (4 boucles imbriquées ici) mais comme je n'ai pas cette information par avance c'est là que je bloque.

**Graffito** · 12/12/2006, 22h36

Bon, c'est en effet plus simple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
procedure CompleteListe(Liste,idxdebutListe,idxfinListe,N,Nmax) 
begin
if N<NMax then begin
  for i=idxdebutListe to idxfinListe do Liste.add(liste[i]+Lettres[N+1])) ;
  Completeliste(Liste,idxfinliste+1,Liste.count-1,N+1,Nmax) ;
  end ;
end ;
// Au départ,on fera :
Liste.clear ; 
Nmax=Lettres.count ; // Nmax=8 pour Lettres="Automate"
liste.add("")            ; // ajouter ""
CompleteListe(Liste,0,0,0,Nmax) ;

**Dark-Seal** · 12/12/2006, 23h50

Ok, cette fois j'ai bien compris ton code. Le hic c'est que je n'arrive pas à l'implémenter en C

(halala, vivement que je reprenne le java).
En tout cas merci Graffito j'vais essayer de me dépatouiller avec ça (et si Nemerle repasse par là j'aimerais bien voir sa méthode plus en profondeur

).

Sur ce, bonne nuit

**Nemerle** · 21/12/2006, 15h50

Envoyé par Dark-Seal

Bon j'ai regardé ton code Nemerle, et j'aurais besoin de quelques éclaircissements si possible ^^

Code :

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

i[j]=j

Je ne comprend pas le but cette affectation, cela ne va pas effacer les i[] précédents ?

Je ne vois pas à quoi sert le k aussi.
Et l'algo que tu présentes ne fait pas L boucles à la suite ? Enfin si on l'applique à mon exemple ça ne fera pas :
char1 : 01
char2 : 01
char3 : 01 ?

Attention, je ne t'ai donné que le début de l'algo!!!

tu cherches tous les mots de longueur l. Tu commences par le mot
M[0]M[1]...M[l-2]M[l-1]
puis tu incrémentes la dernière lettre
M[0]M[1]...M[l-2]M[l]
etc, jusqu'à ce que tu arrives à la "dernière" lettre M[L]:
M[0]M[1]...M[l-2]M[L]
Là, tu incrémentes l'avant dernière lettre, et la dernière suit:
M[0]M[1]...M[l-1]M[l]
...etc...
i[j]=j représente le 1ier mot ci-dessus. Plsu loin dans l'algo tu feras "quelque-chose" comme i[j]=j pour j de k à l, comme dans le 4ième mot ci-dessus! En fait tu feras i[k]=le 1ier indice distinct de i[0]...i[k-1], i[k+1]= le 1ier indice distinct de i[0]...i[k], ... En fait k représente le No de la lettre où tu vas incrémenter son indice de 1 (cf. l'avant dernière lettre de l'ex. ci-dessus, où k=l-1) puis mettre à jour tous les indices supérieurs (tu recommences). Une fois cette MAJ, tu repasses à k=l.

**coyotte507** · 25/12/2006, 16h34

Met le truc "resolu" si t'es arrivé ^^

sinon voila ce que je propose (c'est plutot simple à transformer en C)

J'utilise dans l'algo un truc propre au C: la fin de chaine est un "\0"

Code :

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

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
/* variables
var nbLettres
var pos[nbLettres-1] //tableau dynamique
var longCour
var mot //Le mot, chaine de char
 
 principe:
 * On commence avec tous le mot de 1 possibles, puis de 2, ... jusqu'à n
 * n est nbLettres
 * longCour est la longueur du mot qu'on trouve: au début, elle sera de 1, puis de 2, puis... de n
 * pos: contient les curseurs: au début ils sont tous placés dans l'ordre, puis à chaque nouveau mot, le curseur le plus loin avance: quand il est au bout, c'est le curseur d'avant qui avance et ainsi de suite... Ca permet de parcourir toutes les possibilités
 * i sert a des itérations quelconques
 * tempo est une chaine qui contient le mot temporaire.
 */
 
chaine mot = entrer mot;
entier nbLettres = longueur(mot);
entier pos[nbLettres];
entier longCour = 1;
entier i;
chaine tempo[nbLettres + 1];
 
pour longCour = 1, tant que longCour <= nbLettres, faire longCour ++
{
  pour i = 0, tant que i < longCour, faire i++
  {
    //On initialise les pos de départ: pos[0] = 0, pos[1] = 1...
    pos[i] = i;
  }
 
  toujours faire
  {
    //On forme le mot avec les lettres désignées par le membres de pos
    //On s'arrete lorsqu'on est au bout du mot ou si il n'y a plus de curseur
    pour i=0, tant que pos[i]!= 0 et i<longCour, faire i++
    {
      tempo[i] = pos[i];
    }
    //Caractere de fin de chaine:
    tempo[i+1] = "\0";
    ajouter tempo;
 
    //On bouge le curseur de fin:
    //Si le dernier curseur est à la fin, on vérifie si le curseur d'avant peut avancer et ainsi de suite....
    //Il y a des 1 qui se baladent du fait de la comparaison d'un curseur et d'une longueur (l'un commence à 0, l'autre à 1)
    pour i = longCour-1, tant que i >= 0 et pos[i]=nbLettres-(longCour-(i+1)), faire i--
    { ;
    }
    //On vérifie si la boucle a été exécutée completement: aucun curseur ne peut plus avancer
    si i=0
    {
      sortir de la boucle "toujours faire";
    } sinon 
    {
      pos[i] ++;
    }
  }
}

voila sans commentaires:

Code :

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

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
 
chaine mot = entrer mot;
entier nbLettres = longueur(mot);
entier pos[nbLettres];
entier longCour = 1;
entier i;
chaine tempo[nbLettres + 1];
 
pour longCour = 1, tant que longCour <= nbLettres, faire longCour ++
{
  pour i = 0, tant que i < longCour, faire i++
  {
    pos[i] = i;
  }
 
  toujours faire
  {
    pour i=0, tant que pos[i]!= 0 et i<longCour, faire i++
    {
      tempo[i] = pos[i];
    }
    tempo[i+1] = "\0";
    ajouter tempo;
 
    pour i = longCour-1, tant que i >= 0 et pos[i]=nbLettres-(longCour-(i+1)), faire i--
    { ;
    }
 
    si i=0
    {
      sortir de la boucle "toujours faire";
    } sinon 
    {
      pos[i] ++;
    }
  }
}

Pas de récursivité, juste des boucles... mais un tableau dynamique ^^

EDIT: n'oublie pas avant d'ajouter un mot de vérifier qu'il n'y est pas déjà (par exemple deux mots d'une lettre "T" avec le mot automate

**Nemerle** · 26/12/2006, 14h02

Coyott507, ton algo est sur le bon chemin, mais il est malheureusement incorrect: tu gères correctement ton curseurs (et de façon optimale, bravo!), mais la mise à jour des pos est un peu plus compliquée que cela! Je m'explique: dans

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
    pour i = longCour-1, tant que i >= 0 et pos[i]=nbLettres-(longCour-(i+1)), 
           faire i--
    { ;
    }
    si i=0
    {
      sortir de la boucle "toujours faire";
    } sinon 
    {
      pos[i] ++;
    }

la ligne en rouge n'est pas suffisante. Dans l'exemple ou le mot est "12345", ton algo fait

123
124
125 <- la, le curseur passe correctement de la 3ième lettre à la seconde, et dans ce cas il n'effectue que la ligne en rouge, qui donne :

135 (au lieu de 13"2")

puis comme en plus la 3ième lettre reste à 5, la suite donne:

145
245
345
et basta!

En plus de ta ligne en rouge, il faut que tu remettes à jour les pos[j] pour j>i et j<LongCour, ET CECI en fonction des valeurs deja prises par pos[0]...pos[i].

Tu y es presque

Voila.

**Nemerle** · 26/12/2006, 14h10

Ajout: ton algo doit donner pour le mot "12345" les mots suivant, dans l'ordre de l'algo:

123 124 125
132 134 135
142 143 145
213 214 215
231 234 235
...

Ce que j'avais oublié de dire, c'est que faire simplement pos[i]++ une fois la place du curseur trouvée, n'est pas suffisante --> sinon dans les cas en rouge ci-dessus, tu obtiendrais des valeurs erronées...car tu utiliserais des lettres déjà utilisées dans les pos[j] pour j<i !!

**coyotte507** · 04/01/2007, 15h50

Merci de ton aide ^^
Je vois, en fait il faut que lorsque je fasse

Code :

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

pos[i]++;

, je ramène les curseurs d'après le plus près possible.

Je dois donc faire une boucle pour ramener les curseurs d'après, je les ramène simplement à la valeur du curseur précédent +1 à partir d'un certain curseur.

Sinon, je ne fait pas une recherche exhaustive: les lettres doivent garder le même ordre: en partant de 12345, je ne peut pas avoir 312 car 3 est après 1 et après 2. L'auteur du l'a précisé dans 1 de ses posts. Par contre, je peux avoir 135, ce que je n'aurais pas pu avoir sans ton aide.

En tout cas, merci beaucoup pour m'avoir signalé et expliqué mon erreur sans me donner la solution, ca fait plaisir.

enfin, ca donne:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    pour i = longCour-1, tant que i >= 0 et pos[i]=nbLettres-(longCour-(i+1)), 
           faire i--
    { ;
    }
    si i=0
    {
      sortir de la boucle "toujours faire";
    } sinon 
    {
      pos[i] ++;
      pour i++, tant que pos[i] != 0, faire i++
      {
        pos[i] = pos[i-1] + 1;
      }
    }

au lieu de

Code :

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

1
2
3
4
5
6
7
8
9
10
11
    pour i = longCour-1, tant que i >= 0 et pos[i]=nbLettres-(longCour-(i+1)), 
           faire i--
    { ;
    }
    si i=0
    {
      sortir de la boucle "toujours faire";
    } sinon 
    {
      pos[i] ++;
    }

Enumération des mots d'un automate

Algorithmes et structures de données

Discussions similaires

Partager

Partager