Combinaisons possibles

Question

Combinaisons possibles

Signaler

ElectricalMan

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

- 26 juil. 2006 à 11:53
cs_AlexN

Messages postés: 694
Date d'inscription: lundi 5 décembre 2005
Statut: Membre
Dernière intervention: 8 janvier 2014

- 26 juil. 2006 à 17:59

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
X1b , X2a , X3 , X4a
X1a , X2b , X3 , X4a
X1b , X2b , 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 à Cⁿ_k 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à...

A voir également:

Combinaisons possibles
Algorithme combinaisons sans répétition - Guide
Amigo combinaison gagnante ✓ - Forum - C++ & C++ .NET
Générateur de combinaison loto - Guide
Générer toutes les combinaisons possibles python ✓ - Forum - C
Générer toutes le combinaisons possibles d'une chaîne de caractères - Forum - C

10 réponses

Répondre Posez votre question

vinc1008881 · Answer 1 · 2006-07-26T13:02:56+0200

Réponse 1 / 10

vinc1008881

Messages postés: 257
Date d'inscription: dimanche 22 août 2004
Statut: Membre
Dernière intervention: 29 septembre 2010

3
26 juil. 2006 à 13:02

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.

ElectricalMan · Answer 2 · 2006-07-26T14:00:32+0200

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

ElectricalMan · Answer 3 · 2006-07-26T15:11:57+0200

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;
}

cs_AlexN · Answer 4 · 2006-07-26T15:47:07+0200

Réponse 4 / 10

cs_AlexN

Messages postés: 694
Date d'inscription: lundi 5 décembre 2005
Statut: Membre
Dernière intervention: 8 janvier 2014

15
26 juil. 2006 à 15:47

Ce sujet répond peut être à ta question.

ElectricalMan · Answer 5 · 2006-07-26T16:31:30+0200

Réponse 5 / 10

ElectricalMan

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

26 juil. 2006 à 16:31

à oui c cool ton truc ! merci bcp

j'essaye de l'appliquer...

cs_AlexN · Answer 6 · 2006-07-26T16:44:02+0200

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;
}

ElectricalMan · Answer 7 · 2006-07-26T17:09:44+0200

Réponse 7 / 10

ElectricalMan

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

26 juil. 2006 à 17:09

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

cs_AlexN · Answer 8 · 2006-07-26T17:25:22+0200

Réponse 8 / 10

cs_AlexN

Messages postés: 694
Date d'inscription: lundi 5 décembre 2005
Statut: Membre
Dernière intervention: 8 janvier 2014

15
26 juil. 2006 à 17:25

ok pas vu. Tu veux des quadruplets, j'avais lu des couples Etats/Capteurs.

ElectricalMan · Answer 9 · 2006-07-26T17:47:47+0200

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;

cs_AlexN · Answer 10 · 2006-07-26T17:59:29+0200

Réponse 10 / 10

cs_AlexN

Messages postés: 694
Date d'inscription: lundi 5 décembre 2005
Statut: Membre
Dernière intervention: 8 janvier 2014

15
26 juil. 2006 à 17:59

Oui, _Tabs est un type structure, et _pTabs un pointeur sur ce type de structure.
De rien.

Votre réponse