Génération d'une liste des combinaisons sans répétition d'éléments d'un groupe de tableaux

Contenu du snippet

Le titre est long parce qu'il traduit mon ignorance de ce que fait en terme mathématique cet algorithme (Mais en tout cas, il le fait) :
Si quelqu'un veut suggérer un autre titre, il est le bienvenu.

L'idée était la suivante :

Si on considere 5 (ou m) tableaux de variables (structures) chacun de ces tableaux contient n éléments.
je voudrais calculer toutes les solutions possibles en parcourant chaque tableau et chaque variables.
petit exemple:
Tableau1 Sol1-1 Sol1-2 Sol1-3
Tableau2 Sol2-1 Sol2-2
Tableau3 Sol3-1 Sol3-2 Sol3-3 Sol3-4
Tableau4 Sol4-1 Sol4-2 Sol4-3
Tableau5 Sol5-1 Sol5-2

La premiere solution globale serait:
Sol1-1,Sol2-1,Sol3-1,Sol4-1,Sol5-1
La deuxieme
Sol1-1,Sol2-1,Sol3-1,Sol4-1,Sol5-2
La troisieme
Sol1-1,Sol2-1,Sol3-1,Sol4-2,Sol5-1
etc...

Source / Exemple :


#include "stdafx.h" // Pour windows uniquement
#include <stdlib.h>
#include <string.h>
#include <time.h>

// Changer ici le nombre de tableaux a traiter
// (Doit être connu à la compilation)
#define MAXTAB 3
#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];

// Calcul et affichage des solutions
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;
}

A voir également

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.