Amelioration d'un algorithme de permutation...

Question

Salut a tous! Dans l'idee de fraire un programme (en C console) ki teste toutes les possibilit&#233; d'une chaine de (8) caract&#232;res, les stock dan un tableau de poiniteurs vers chaines et de trouver les mots de la langue francaise que l'on peut former avec, j'ai &#233;cri cet algo mais je me demande si il y a pa moyen de l'ameliorer ou plutot kil soit plu adaptable. Peut-&#234;tre avec unen recursivit&#233; ou je ne sai koi pour eviter davoir a creer une boucle de plus a chaque lettre de plus dan la chaine de caracteres...



<HR>



void Toutes_combinaisons(
char *chaine, 
int n, 
char *tab_combinaisons[])


{



int i, j, k, l, m, o, p = 0;



char chaine_base[10], chaine_5[10], chaine_6[10], chaine_7[10], chaine_8[10];


strcpy(chaine_base, chaine);



for(o = 0 ; o < 8 ; o++)


{


strcpy(chaine, chaine_base);


Permutation(chaine, n-8, n-8+o);


strcpy(chaine_8, chaine);



for(m = 0 ; m < 7 ; m++)


{


strcpy(chaine, chaine_8);


Permutation(chaine, n-7, n-7+m);


strcpy(chaine_7, chaine);



for(l = 0 ; l < 6 ; l++)


{


strcpy(chaine, chaine_7);


Permutation(chaine, n-6, n-6+l);


strcpy(chaine_6, chaine);



for(k = 0 ; k < 5 ; k++)


{


strcpy(chaine, chaine_6);


Permutation(chaine, n-5, n-5+k);


strcpy(chaine_5, chaine);



for(j = 0 ; j < 4 ; j++)


{


strcpy(chaine, chaine_5);


Permutation(chaine, n-4, n-4+j); 



for(i = 0 ; i < 3 ; i++)


{


tab_combinaisons[p] = (
char *) malloc(8 * 
sizeof(
char));


strcpy(tab_combinaisons[p], chaine);


p++;


Permutation(chaine, n-2, n-1);


tab_combinaisons[p] = (
char *) malloc(8 * 
sizeof(
char));


strcpy(tab_combinaisons[p], chaine);


p++;


Permutation(chaine, n-3, n-2);


} 


} 


} 


}


}


}


}

Voila merci de repondre toutes reponse m'interesse, c'est pour progresser (dsl pour le code ki a perdu c espaces : comment on fai popur ajouter du code proprement )

vecchio56 · Answer

Petit calcul rapide: il y a 26^8 mots de 8 lettres possible (sans tenir compte des accents). Pour stoker ca, il te faudra environ 200Go, donc il faut surtout pas stocker.
Par contre, je vois pas comment tu vuex trouver les mots francais avec ca, il faut bien écrire une liste à un moment donné.

vecchio56 · Answer

Par exemple, tu peux utiliser cette liste: http://www.bellamyjc.net/download/dicofr.zip

cs_Torin · Answer

Merci pour le lien...
Par contre moi je ne voi pa 26^8 possibilit&#233; mais 8! ( factorielle de 8) soit 40320 ce qui se stock facilement ( qq mo de memoire max ), donc pa de problemen ca marhce jai essaye avec un dico et tout.
Le seul truc que j'aimerai faire c rendre la fonction plus adaptable qu'elle puisse permuter 7 - 8 - 9 &#233;l&#233;ments...Et je sui quasi-persuad&#233; que ca peut s'ecrire de facon recursive parce que trouver ltoutes les permutaion de n revien a trouver toutes les permutation de n-1 etc........

vecchio56 · Answer

Il y a 26 lettres dans l'alphabet, donc pour chaque lettre tu a 26 possibilités, soit donc 26*26*26*26*26*26*26*26 mots, qu'on écrit aussi 26^8
A moins que tu m'expliques d'ou vient ton 8!

cs_Torin · Answer

J'ai mal exposer le probleme, en fait la fonction est apell&#233; avec comme argument un pointeur vers une chaine de 8 caract&#232;res.
Il y a donc 40320 possibilit&#233; de permutations : 12345678, 12345687, 12345867........82345671
Voila j'espere que vous avez compri mon probleme maintenantqui est de rendre adaptable la fonction pour quelle fassent jusqu'a 9 caracteres san avoir 9 boucles for...en fonction de la chaine qu'on lui envoie.

ctx_man · Answer

Je dois pas etre bien r&#233;veiller, j'ai pas beacoup dormit. Mais je n'ai pas trouver ta fonction de permutation, je ne sais pas ce qu'elle fait.
Pour optimiser ton code cherche du coter de la creation et du parcour d'arbres binaires. Je suis sur que tu trouvera ton bonheure.

Le travail c'est la sant&#233;, ne rien faire c'est la pr&#233;serv&#233; !!!

cs_Torin · Answer

En fait, l'algo realise toutes les permutaions d'une chaine de 8 caracteres et les stock dans un tab de pointeurs , la fonction Permutation() ne faisant que changer deux &#233;l&#233;ments de la chaine entre eux et que j'ai oubli&#233; de presenter, je vou la donne : 
void Permutation(char *chaine, int x, int y)
{
 char buffer;
 buffer = chaine[x];
 chaine[x] = chaine[y];
 chaine[y] = buffer;
}Sur 4 caracteres, il y a 24 possibilit&#233;s : 1234-1243-1423-1432-1324-1342-2134 6 possibilit&#233;es * 4 24 soi 4! (factorielle de 4) = 24.
L'algo fait donc cette operation sur 8 lettres avec 8 boucles for que j'aimerais simplement remplacer par une fonction recursive si possible pour qu'il soit plus adaptable . Merci pour les conseils  ctx_man, ca doit etre pratique dans mon exemple un arbre binaire mais ca me semble compliquer ( sauf si on m'eclaircit ) et je ne voi pa de quelle facon y arriver..

Amelioration d'un algorithme de permutation...

7 réponses

Votre réponse

Discussions similaires