Combinaisons possibles

Signaler
Messages postés
39
Date d'inscription
samedi 20 mars 2004
Statut
Membre
Dernière intervention
5 novembre 2008
-
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
-
slt tt le monde,   
j'ai un ensemble de paramètres avec différentes valeurs possibles !!!    je m'explique :
si au départ j'ai un ensemble de 4 param, avec pour chaque param plrs valeurs possibles. par exp :  X1a / X1b  ,  X2a / X2b  ,  X3  ,  X4a / X4b / X4c
je souhaite générer les combainaisons possibles, sachant que je ne m'intéresse pas à l'ordre des param (donc pas de permutations). j'obtiendrai :
X1a , X2a , X3 , X4a
X1bX2a , X3 , X4a
X1a , X2b , X3 , X4a
X1bX2b , X3 , X4a
...

je sais pas si qq est fort en proba et qui pourrait me dire quelle formule permettrait de calculer le nbre de combinaisons possibles. je pensai au départ à Cnk  avec dans cet exp : n=8 et k=4. une fois on calcul ts les ensembles de 4 param,
1) On élimine les ensembles qui ne contiennent pas une valeur de chaque param ! par exp :
X1a , X1b , X2a , X4a   ; pas de 3eme param
X1a , X3 , X4a , X4c  ; pas de 2eme param
...
2) On élimine les combinaison de même param (avec permutations) :
X1a , X2a , X3 , X4a
X3 , X2a , X1a , X4a  ->  à éliminer ; même param que la précédente

bref vous m'avez compris... 

et puis bien sure si vous pouver m'aider avec un bout de code ou même un algo 
voilà voilà...

10 réponses

Messages postés
257
Date d'inscription
dimanche 22 août 2004
Statut
Membre
Dernière intervention
29 septembre 2010
3
bref vous m'avez compris... >> pas exactement...

bon si tu ne t'interresse pas à l'ordre alors on peut faire une hypothese non restrictive : on a toujours : X1x, X2y, X3z...

pour le premier paramètre tu a n choix de valeur,
pour le premier paramètre tu a m choix de valeur,
.....

donc au final tu as n*m*o... combinaisons.

Après je suis pas sur d'avoir bien compris ton problème.
Messages postés
39
Date d'inscription
samedi 20 mars 2004
Statut
Membre
Dernière intervention
5 novembre 2008

merci  vinc1008881

oui c bien ça ; on a toujours : X1x, X2y, X3z...
et t'as raison aussi, y'a :  n*m*...  combinaisons

donc maintenant mon pb, aaah ! :

- je pars d'un fichier text du type ; etat1_a/etat1_b,eta2_a/etat2_b,etat3,etat4_a/etat4_b      capt1_1, capt2_1, capt3_1
etat1_c/etat1_d,eta2_a/etat2_b,etat3,etat4_c/etat4_d      capt1_3, capt2_1, capt3_2
...

en fait c des états de différents automates modèlisant le comportement de composants d'un système. à droite j'ai les valeurs capteurs corresponadantes ;   chaque ligne correspond à ce que je nomme par :  un couple Etats/Capteurs
ça m'informe sur l'état de mon système...  !!!  ça c pour la ptite histoire.
donc moi je souhaite générer un autre fichier avec cette fois-ci ttes les combinaisons avec un état par modèle ;
etat1_a,eta2_a,etat3,etat4_a      capt1_1, capt2_1, capt3_1
etat1_b,eta2_a,etat3,etat4_a      capt1_1, capt2_1, capt3_1
...
etat1_c,eta2_a,etat3,etat4_c      capt1_3, capt2_1, capt3_2
etat1_d,eta2_a,etat3,etat4_c      capt1_3, capt2_1, capt3_2
...

donc pour le moment j'arrive à lire ligne par ligne le fichier, je sépare les différents paramètres. pour cela j'utilise une fonction  split  ;  char** split( char* str, const char* separateur).

int main(int argc, char *argv[])
{
char fichier_data[255];
FILE *fic=NULL;
long nbrCouples=0, nbrEtats=0, tailleStr=255, i=0, j=0;
char *coupleEtatsCapteurs=NULL;
char **cpsCouple=NULL, **cpsEtats=NULL, **cpsCapteurs=NULL, **cpsMemeEtat=NULL;
 // ----------- Initialisations ----------------
 const char *chemin = "c:\\user\\............";
 sprintf(input, "%sRep\\fichier_data.dat", chemin);
   
 fic = fopen(input,"r"); // ouverture du fichier input en mode lecture
 if(fic == NULL)  exit(0); 

 coupleEtatsCapteurs = malloc( (tailleStr) * sizeof(*coupleEtatsCapteurs) ); 
 if (coupleEtatsCapteurs == NULL)   exit(0);

// ----------- Lecture des paramètres du fichier  ----------------

 rewind(fic); // repositionner le curseur au début de "fic"
 nbrCouples = 0; // Réinitialisation ( au cas où ! )
 while( fgets(coupleEtatsCapteurs, tailleStr, fic) != NULL ) 
 { // On lit fic (ligne par ligne) tant qu'on ne reçoit pas d'erreur (NULL)
  
     if( strcmp(coupleEtatsCapteurs, "\n") )
     { // Si ligne non vide

             // Virer l'\n à la fin (de la ligne lue)
         coupleEtatsCapteurs[strlen(coupleEtatsCapteurs) - 1] = '\0'; 

              // Séparer les couples Etats/Capteurs en 2 chaines : 
               // l'ensemble des états et l'ensemble des valeurs capteurs
         cpsCouple = split(coupleEtatsCapteurs, "\t"); 
 
             // Extraire les différents états d'un couple 
         cpsEtats = split(cpsCouple[0], ",");
   

         for(i=0; cpsEtats[i]; i++) 
         {
                 // Extraire les différents vals d'un même état 
       
     cpsMemeEtat = split(cpsEtats[i], "/");
             for(j=0; cpsMemeEtat[j]; j++) 
             {                
   
                  //printf("%d : %s\n", j, cpsMemeEtat[j]);    

             }
      
   }
      
             // Extraire les différents valeurs Capteurs d'un couple 
         cpsCapteurs = split(cpsCouple[1], ",");
         for(i=0; cpsCapteurs[i]; i++) 
         {
                //printf("%d : %s\n", i, cpsCapteurs[i]);    

         }
      
         free(cpsEtats);  // important : libérer
         free(cpsMemeEtat);
         free(cpsCapteurs);
         free(cpsCouple);      // je vous l'accorde y'a bcp de free
   
         nbrCouples++; // compter le nombres de couples (= lignes non vides)      
     }
 }
 
 printf("\nnbre de couples : %ld\n", nbrCouples);   // juste pour info
 

 fclose(fic);
 free(coupleEtatsCapteurs);


donc 2 Q :

1) déjà si l'opération de "séparation" des différentes chaines vous semble trop longue, dite moi si y'a un autre moyen (je débute en programmation !)

2) je souhaite maintenant générer les différentes combi et les écrire dans un nouveau fichier.

merci pour tout
Messages postés
39
Date d'inscription
samedi 20 mars 2004
Statut
Membre
Dernière intervention
5 novembre 2008

juste à titre d'info, voici la fct split(que j'ai récupéré de je ne sais d'où ?!) :




//-----------------------------------------------------------------
// Extraction de mots d'une chaine, à partir d'un "séparateur"
//-----------------------------------------------------------------
char** split( char* str, const char* separateur)
{
size_t   sizeSeparateur=strlen( separateur );
char**   currentSplit=0;
size_t   nbSep=0, sizeSplit=0, currentSep=0;
char*   pos=str, *currentPos=str;

 
     // Compter le nombre de séparateur, et remplacer le séparateur par des '\0'
    while( pos = strstr( pos, separateur ) ) 
    {
        memset( pos, '\0', sizeSeparateur );
        ++nbSep;
        currentPos = (pos += sizeSeparateur);
    }
    
       // Calculer la taille du tableau final
    sizeSplit = nbSep+1 ; 
    if ( !sizeSplit ) 
       return 0;
    
       // Allouer le tableau des pointeurs
    currentSplit = malloc( (sizeSplit+1) * sizeof(char*) );
    if ( !currentSplit ) 
       return 0;

    currentSplit[sizeSplit] = 0;   // j'ai rajouté ça : 
        // ça me permettra après (dans main.c) de faire le test: for(i=0;tab[i];i++)
 
       // Affecter les entrées du tableau
    pos = str;
    while( currentSep < sizeSplit ) 
    {
        currentSplit[currentSep++] = pos;
        while( *pos++ );
        pos += sizeSeparateur - 1;
    }



   return currentSplit;
}
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
15
Ce sujet répond peut être à ta question.
Messages postés
39
Date d'inscription
samedi 20 mars 2004
Statut
Membre
Dernière intervention
5 novembre 2008

à oui c cool ton truc !  merci bcp


j'essaye de l'appliquer...
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
15
Quelques modifications, il y a un paramètre redondant (IdxTab et Niveau) dans la fonction AfficherSol, il faut en enlever 1.
Et dans ton cas, il n'y a que 2 tableaux.

#include "stdafx.h"
#include <stdlib.h>
#include <string.h>
#include <time.h>

// Changer ici le nombre de tableaux a traiter
// (Doit être connu à la compilation)
#define MAXTAB 2
#define TAILLE 7
#define MAXRAND 5

typedef struct {
    int Dim; // Taille du tableau
    char **Tab; // Tableau de chaines ("Sol1-1", "Sol1-2"..)
} _Tabs, *_pTabs;

typedef int SubTab[MAXTAB];

// Et hop !
void AfficherSol (_pTabs Tabs, SubTab Index, int Niveau) {  

    int IdxEle;

    if ( Niveau == MAXTAB ) {
        for ( int Idx = 0; Idx < MAXTAB; Idx++ )
            printf ("%s ", Tabs[Idx].Tab[Index[Idx]]);
        puts("");
        return;
    }
    for (IdxEle = 0 ; IdxEle < (*(Tabs+Niveau)).Dim ; IdxEle++ ) {
        Index[Niveau] = IdxEle;
        AfficherSol (Tabs, Index, Niveau+1);
    }
}

int main(int argc, char* argv[]) {

    _Tabs Tabs[MAXTAB];
    int IdxTab, IdxEle;
    char Element[TAILLE];
    SubTab Index;

    // Création des tableaux
    srand((unsigned)time( NULL ));
    for ( IdxTab = 0; IdxTab < MAXTAB; IdxTab++ ) {
        Tabs[IdxTab].Dim = rand()%MAXRAND + 1;
        Tabs[IdxTab].Tab = (char **) malloc (sizeof(char *)*Tabs[IdxTab].Dim);
        for ( IdxEle = 0; IdxEle < Tabs[IdxTab].Dim; IdxEle++ ) {
            Tabs[IdxTab].Tab[IdxEle] = (char *) malloc (sizeof(char)*TAILLE);
            sprintf (Element, "Sol%1d-%1d", IdxTab+1, IdxEle+1);
            strcpy (Tabs[IdxTab].Tab[IdxEle], Element);
        }
    }
    // Affichage des tableaux
    for ( IdxTab = 0; IdxTab < MAXTAB; IdxTab++ ) {
        printf ("Tableau numero %d : ", IdxTab+1);
        for ( IdxEle = 0; IdxEle < Tabs[IdxTab].Dim; IdxEle++)
            printf ("%s ", Tabs[IdxTab].Tab[IdxEle]);
        puts("");
    }
    puts("");
    // Affichage de la solution
    AfficherSol((_pTabs) &Tabs, Index, 0);
    return 0;
}
Messages postés
39
Date d'inscription
samedi 20 mars 2004
Statut
Membre
Dernière intervention
5 novembre 2008

il y a un paramètre redondant (IdxTab et Niveau) dans la fonction AfficherSol, il faut en enlever 1. >>    oui t'as raison. merci...

Et dans ton cas, il n'y a que 2 tableaux. >>    plutôt 4 !   
par exp pour la 1ere ligne (etat1_a/etat1_b,eta2_a/etat2_b,etat3,etat4_a/etat4_b) j'ai :
tableau1 :  etat1_a / etat1_b
tableau2 :  eta2_a / etat2_b
tableau3 :  etat3
tableau4 :  etat4_a / etat4_b
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
15
ok pas vu. Tu veux des quadruplets, j'avais lu des couples Etats/Capteurs.
Messages postés
39
Date d'inscription
samedi 20 mars 2004
Statut
Membre
Dernière intervention
5 novembre 2008

j'avais lu des couples Etats/Capteurs.
>>  oui t'as raison, c pas clair ! ;
par exp pour la 1ere ligne ;
etat1_a/etat1_b,eta2_a/etat2_b,etat3,etat4_a/etat4_b      capt1_1,capt2_1,capt3_1
j'ai :
Etats : etat1_a/etat1_b,eta2_a/etat2_b,etat3,etat4_a/etat4_b

Capteurs : capt1_1,capt2_1,capt3_1

donc les val capteurs je m'en ...   c les états que je retraite.

bref, merci pour le code, tu me sauve la vie. en plus ça me permet d'économiser de l'énèrgie, avec cette chaleur 

NB : ça m'a permis aussi de voir un exp concret d'utilisation de pointeur de structure, c ça non ?! (et oui je maitrise pas encore !) ;
typedef struct
{
    long Dim; // Taille du tableau
    char **Tab; // Tableau de chaines ("Sol1-1", "Sol1-2"..)
} _Tabs, *_pTabs;
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
15
Oui, _Tabs est un type structure, et _pTabs un pointeur sur ce type de structure.
De rien.