[casse-tête]Lister toutes les combinaisons possibles sans ordreRésolu

Question

Salut à tous !

Je cherche depuis ce matin l'algorithme qui permettrai de lister toutes les combinaisons possibles, sans ordre (c'est à dire que ABE équivaut à EBA) de n lettres (n=8 maximum)

Prenons le pire cas:
c'est à dire que je choisi 8 lettres (de A à H) et je dois lister toutes les combinaisons de 1,2,3,4,...,8 lettres possibles avec les lettres choisies. 
il existe 2^8 possibilités (256)

par exemple pour 4 lettres ABCD, 
il y a 0 combinaisons de 0 lettres
il y à 4 combinaisons de 1 lettres (A,B,C,D)
il y à 6 combinaisons de 2 lettres (AB,AC,AD,BC,BD,CD)
il y à 4 combinaisons de 3 lettres (ABC,ABD,ACD,BCD)
il y à 1 combinaisons de 4 lettres (ABCD)

Je ne sais pas à l'avance de combien de lettres je dispose.

j'ai essayé de faire un système avec des for() et c'est assez prise de tête. alors j'ai pensé à un système aléatoire qui fais des combinaisons et qui s'arrete quand il en à trouvé 256 distinctes, mais ça risque d'etre lourd et long...

je vous remercie beaucoup si vous connaissez la solution ou pouvez m'aiguiller. Je précise que je travaille en SQC (autant dire en C)
++
BiLLKiLL

cosmobob · Accepted Answer

salut ;)
'il existe 2^8 possibilités (256)' => yen a 255, vu que tu exclus le cas ou t'as 0 lettre.
ca se fait de facon pas trop compliquée recursivement sinon.

tu cherches a trouver les combinaisons de n lettres parmis 8, sachant que tu connais les combinaisons de n-1 lettres parmis 8.

E = ensemble des combinaisons de n-1 lettres parmis 8.
L = ensemble vide;

pour X dans E faire :
pour i entre 1 et 8 faire :
si i n'est pas dans X et (X U i) n'est pas dans L : L = { L, (X U i) }
fin pour;
fin pour;

a toi de programmer la fonction qui gere les ensembles.
sinon ya deja une gestion des ensembles dans la librairie standard du C++,  a toi de la voir plus précisement...

sinon tu peux te debrouiller avec des tableaux, vu que tu connais par avant la taille de ta liste L ( sa taille est C(n,p) = n! / (p! . (n-p)!) pour les combinaisons de p lettres parmis n)

a+ ;)

cs_AlexMAN · Answer

"il y à 1 combinaisons de 4 lettres (ABCD)"
il ya bocou plus de combinaisons !
Si j'ai bien compris ce ke tu veux faire, ya ABCD, ABDC, BADC....Enfin bocou koi !

Va sur vbfrance.com, 2sources sont presentes : une de Proviste et l'autre de je ne sais ki..En espérant ke ca puisse t'aider..

++

Stepharcher · Answer

Tu as besoin du triangle de Pascal. Ca donne un truc comme ça
0 -> 1
1 -> 1 1
2 -> 1 2 1
3 -> 1 3 3 1
4 -> 1 4 6 4 1       ( <- ça c'est ton cas )

j'explique : au niveau des extrémités, c'est toujours 1,
sinon pour chaque élement, tu prends celui qui est au dessus de lui et tu l'additionnes avec celui qui est au dessus à gauche... C'est facile à faire.

 >:)  Stéph  >:)

Stepharcher · Answer

Tu peux aussi regarder sur
http://www.mjc-andre.org/pages/amej/glossair/entrees/pascalt.html

 >:)  Stéph  >:)

cs_willbill · Answer

AlexMAN: J'ai précisé que l'ordre ne m'intéressai pas. donc ABCD=ACBD dans mon cas

Stepharcher: Sauf erreur de ma part, le triangle de Pascal me permet de compter le nombre de possibilités totales, mais moi je veux lister ces possibilités, pas seulement savoir combien il en existe (cela peut également etre fait tres simplement avec les formules de Combinaisons utilisées en probabilité). 
Si le triangle me permet de les lister, alors j'aimerai plus de détails et je m'excuse pour la phrase précédente.

Merci à tous les 2 pour vos réponses ;) 
 
BiLLKiLL

dletozeun · Answer

ET si tu faisait un arbre? Fo essayer d'adapter au c ensuite...

cs_willbill · Answer

dletozeun: la méthode proposée par cosmobob s'assimile à un arbre, puisque si j'ai bien compris, on prend chacun des éléments de l'ensemble précécédent comme point de départ pour trouver l'ensemble cherché.

Je vais chercher la manière la plus simple de gérer les ensembles ou bien faire par tableau. Mais je suis en C et non en C++ donc je ne sais pas si ça existe aussi.

Merci beaucoup Cosmo !!
Je vous donne des news bientôt ;)

BiLLKiLL

cs_willbill · Answer

A prioris ça va marcher, merci cosmob, je vous filerai le code quand j'aurai terminé. je marche avec un tableau de structures.

cs_willbill · Answer

Je fais du C que depuis quelques jours donc n'y allez pas les yeux fermés ! // Struct.c :: Utilisation des structures #include #include #define nb_ci 8 /*nombre de choix possibles/* #define nb_cases 70 /* correspond environ au nombre de combinaisons de nb_ci/2 dans nb_ci */ #define lg_cases 15 /*correspond environ à 2*nb_ci*/ typedef char *chaine; typedef struct ens { char cb[nb_cases][lg_cases]; int card; }ens2; typedef ens2 *Pens; /* fonctions de calculs */ unsigned short facto(int n) { unsigned short result=1; int i; for (i=n;i>0;i--) { result=result*i; } return result; } /*################*/ unsigned short Cnp(int p,int n) //Calcule le nombde de combinaisons sans ordre si on prent P éléments parmis N avec 0<=P<=N { unsigned short somme=(facto(n)/(facto(p)*facto(n-p))); return somme; } /* Corps du programme */ Pens T[nb_ci]; int main(int argc, char* argv[]) { printf(" Début du Programme;"); /* Raisonnement par récurrence */ /* Conditions initiales */ T[0]=(ens2*)malloc(sizeof(ens2)); T[0]->card=Cnp(0,nb_ci); strcpy(T[0]->cb[0],""); /* Transmission */ int I,J,K,i,j,start,somme; char combinaison[lg_cases],plop[lg_cases],last_nb[3]; somme=0; for(I=1;I<=nb_ci;I++) { T[I]=(ens2*)malloc(sizeof(ens2)); T[I]->card=Cnp(I,nb_ci); printf(" Il y à %u façons de prendre %d Elements parmis %i :",T[I]->card,I,nb_ci); somme=somme+T[I]->card; i=0; for(J=0;J<(T[I-1]->card);J++) { /* On récupère le dernier numéro de la chaine pour pouvoir partir du numero suivant (ainsi on evite 2#2 en passant à 2#3 direct) */ sprintf(plop,"%s",T[I-1]->cb[J]); start=0; sprintf(last_nb,""); for(j=0;j<(strlen(plop));j++) { if(plop[j]=='#') {sprintf(last_nb,"");} else {sprintf(last_nb,"%s%c",last_nb,plop[j]);} } start=atoi(last_nb)+1; /*printf(" Dep:%i",start); */ for(K=start;K<=nb_ci;K++) { if(I==1) {sprintf(combinaison,"%d",K);} else {sprintf(combinaison,"%s#%d",(T[I-1]->cb[J]),K);} strcpy(T[I]->cb[i++],combinaison); printf(" %s",combinaison); } } } printf(" %d resultats trouvés !",somme); /* Libération de la mémoire pour tous les tableaux */ for(I=0;I<=nb_ci;I++) { free(T[I]); } printf(" Mémoire libérée; Fin du programme; "); return 0; } BiLLKiLL

cosmobob · Answer

ben c'est pas mal, en+ ca marche!

borgeomi · Answer

Bonjour


je cherche un algorithme semblable en Visual basic ????



 


borgeomibonjouuuuuuur !!!!!

[casse-tête]Lister toutes les combinaisons possibles sans ordre

11 réponses

Votre réponse

Discussions similaires