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

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

"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..

++

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

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

Stéph

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

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

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

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

Je fais du C que depuis quelques jours donc n'y allez pas les yeux fermés !

// Struct.c :: Utilisation des structures #include <stdio.h> #include <malloc.h> #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("\nDé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("\n 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("\n 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("\n%s",combinaison); } } } printf("\n\n %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("\nMémoire libérée;\nFin du programme;\n"); return 0; }

BiLLKiLL