Amelioration d'un algorithme de permutation...

Signaler
Messages postés
4
Date d'inscription
dimanche 23 octobre 2005
Statut
Membre
Dernière intervention
29 décembre 2005
-
Messages postés
4
Date d'inscription
dimanche 23 octobre 2005
Statut
Membre
Dernière intervention
29 décembre 2005
-
Salut a tous! Dans l'idee de fraire un programme (en C console) ki teste toutes les possibilité d'une chaine de (8) caractè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 écri cet algo mais je me demande si il y a pa moyen de l'ameliorer ou plutot kil soit plu adaptable. Peut-être avec unen recursivité 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 )
A voir également:

7 réponses

Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
8
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é.
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
8
Par exemple, tu peux utiliser cette liste: http://www.bellamyjc.net/download/dicofr.zip
Messages postés
4
Date d'inscription
dimanche 23 octobre 2005
Statut
Membre
Dernière intervention
29 décembre 2005

Merci pour le lien...
Par contre moi je ne voi pa 26^8 possibilité 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 éléments...Et je sui quasi-persuadé 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........
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
8
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!
Messages postés
4
Date d'inscription
dimanche 23 octobre 2005
Statut
Membre
Dernière intervention
29 décembre 2005

J'ai mal exposer le probleme, en fait la fonction est apellé avec comme argument un pointeur vers une chaine de 8 caractères.
Il y a donc 40320 possibilité 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.
Messages postés
285
Date d'inscription
mardi 28 décembre 2004
Statut
Membre
Dernière intervention
20 janvier 2013

Je dois pas etre bien ré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é, ne rien faire c'est la préservé !!!
Messages postés
4
Date d'inscription
dimanche 23 octobre 2005
Statut
Membre
Dernière intervention
29 décembre 2005

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 éléments de la chaine entre eux et que j'ai oublié 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és : 1234-1243-1423-1432-1324-1342-2134 6 possibilité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..