Discussion :

[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", "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]

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.

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]

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]

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]

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

[Dark-Seal]

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]

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]

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]

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) ;

[Nemerle]

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]

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]

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.