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

cs_willbill 12 Messages postés jeudi 22 juillet 2004Date d'inscription 22 juillet 2004 Dernière intervention - 22 juil. 2004 à 18:20 - Dernière réponse : borgeomi 77 Messages postés mercredi 20 juin 2001Date d'inscription 23 juin 2011 Dernière intervention
- 25 mars 2006 à 15:17
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
Afficher la suite 

Votre réponse

11 réponses

Meilleure réponse
cosmobob 706 Messages postés mardi 30 décembre 2003Date d'inscription 27 janvier 2009 Dernière intervention - 22 juil. 2004 à 21:56
3
Merci
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+ ;)

Merci cosmobob 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 74 internautes ce mois-ci

Commenter la réponse de cosmobob
cs_AlexMAN 1537 Messages postés samedi 21 décembre 2002Date d'inscription 24 mai 2009 Dernière intervention - 22 juil. 2004 à 19:51
0
Merci
"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..

++
Commenter la réponse de cs_AlexMAN
Stepharcher 117 Messages postés samedi 12 avril 2003Date d'inscription 8 septembre 2008 Dernière intervention - 22 juil. 2004 à 20:05
0
Merci
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 >:)
Commenter la réponse de Stepharcher
Stepharcher 117 Messages postés samedi 12 avril 2003Date d'inscription 8 septembre 2008 Dernière intervention - 22 juil. 2004 à 20:06
0
Merci
Tu peux aussi regarder sur
http://www.mjc-andre.org/pages/amej/glossair/entrees/pascalt.html

>:) Stéph >:)
Commenter la réponse de Stepharcher
cs_willbill 12 Messages postés jeudi 22 juillet 2004Date d'inscription 22 juillet 2004 Dernière intervention - 22 juil. 2004 à 21:09
0
Merci
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
Commenter la réponse de cs_willbill
dletozeun 546 Messages postés vendredi 13 février 2004Date d'inscription 9 janvier 2008 Dernière intervention - 22 juil. 2004 à 23:04
0
Merci
ET si tu faisait un arbre? Fo essayer d'adapter au c ensuite...
Commenter la réponse de dletozeun
cs_willbill 12 Messages postés jeudi 22 juillet 2004Date d'inscription 22 juillet 2004 Dernière intervention - 23 juil. 2004 à 09:42
0
Merci
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
Commenter la réponse de cs_willbill
cs_willbill 12 Messages postés jeudi 22 juillet 2004Date d'inscription 22 juillet 2004 Dernière intervention - 23 juil. 2004 à 12:15
0
Merci
A prioris ça va marcher, merci cosmob, je vous filerai le code quand j'aurai terminé. je marche avec un tableau de structures.
Commenter la réponse de cs_willbill
cs_willbill 12 Messages postés jeudi 22 juillet 2004Date d'inscription 22 juillet 2004 Dernière intervention - 26 juil. 2004 à 10:31
0
Merci
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
Commenter la réponse de cs_willbill
cosmobob 706 Messages postés mardi 30 décembre 2003Date d'inscription 27 janvier 2009 Dernière intervention - 26 juil. 2004 à 14:23
0
Merci
ben c'est pas mal, en+ ca marche!
Commenter la réponse de cosmobob
borgeomi 77 Messages postés mercredi 20 juin 2001Date d'inscription 23 juin 2011 Dernière intervention - 25 mars 2006 à 15:17
0
Merci
Bonjour


je cherche un algorithme semblable en Visual basic ????






borgeomibonjouuuuuuur !!!!!
Commenter la réponse de borgeomi

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.