Discussion :

[Invité]

Bonjour tout le monde,

Je souhaite réaliser les combinaisons de n listes de tailles différentes (le nombre de caractères par combinaison est égal à n aussi), par exemple si pour n=3 j'ai les listes suivantes:
l1={a, b, c} ; l2={c, d} et l3={f, j}
Je voudrais pouvoir afficher:
acf
acj
adf
adj

bcf
bcj
bdf
bdj

ccf
ccj
cdf
cdj

Vous me direz j'imbrique 3 for et le tour est joué! Cependant je veux que ma fonction puisse faire cela pour n ensembles donnés en pamaramètre: il faut donc que je fasse un appel récursif, mais je n'arrive pas à trouver comment faire...

Voici un exemple réalisé en imbriquant des boucles for (itératif) pour n=3:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
	for(i=0; i<liste[0]->size; i++)
		for(j=0; j<liste[1]->size; j++)
			for(k=0; k<liste[2]->size; k++)
			{
				printf("%c", listIth(liste[0], i+1) );
				printf("%c", listIth(liste[1], j+1) );
				printf("%c", listIth(liste[2], k+1) );
			}

PS: liste[] est un tableau de n listes (il a donc une taille n)
char lislth(List list, int i) est une fonction qui me retourne la ième valeur de la liste


Merci d'avance

[Steph_ng8]

Bonsoir.
Voici une version récursive.
Attention, elle est incomplète...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void combinations(List lists[], int cpts[], int size)
{
    int i;
 
    for (i = 0; i < size; ++i)
        printf("%c", listInth(lists[i], cpts[i]));
    putchar('\n');
 
    i = size;
    do {
        --i;
        if (cpts[i] == lists[i]->size)
            cpts[i] = 1;
        else
            ++cpts[i];
    } while (cpts[i] != 1);
 
    return combinations(lists, cpts, size);
}

[Edit]En fait, c'est quasiment une version itérative...[/Edit]

[Invité]

Merci de ta réponse mais je ne comprend pas très bien le principe de ton programme ?

[Steph_ng8]

Arf...

Bon, pour commencer, vu que tu as n ensembles à parcourir, il te faut n compteurs (ou indices), un par ensemble.
Tu as un tableau pour les listes, donc ça paraît cohérent d'avoir un tableau pour les compteurs.

La première partie de mon programme affiche l'élément courant de chaque ensemble.
En gros, c'est le contenu de ta boucle for la plus intérieure.

La seconde partie met à jour les différents compteurs.
Comme les trois parties (initialisation, condition, mise à jour) des boucles for.
On commence par incrémenter l'indice de la boucle la plus intérieure ; donc ici, le dernier.
Si on a parcouru tout l'ensemble, alors il faut incrémenter l'indice de la boucle juste englobante, réinitialiser celui de la boucle la plus intérieure.
Et ainsi de suite...

Pour finir, on rappelle la fonction, avec les bonnes valeurs pour les indices.

Mais comme je le disais, elle est incomplète.
Il manque un petit quelque chose pour qu'elle soit utilisable.
Et comme je le faisais remarquer également, il n'y a pas grand chose à changer pour obtenir une version itérative.

[Invité]

Merci beaucoup!
J'ai légèrement modifié ton programme et ça marche !
Dis moi ce que tu en penses?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void Combinations(List lists[], int cpts[], int size)
{
	int i, out=0;
 
	for(i=0; i<size; ++i)
		printf("%c", listIth(lists[i], cpts[i]) );
	printf("\n");
 
	i=size;
	do{
		--i;
		out=0;
		if( cpts[i] == lists[i]->size)
		{
			if(i==0)
				return;
			else
				cpts[i]=1;
		}
		else
		{
			++cpts[i];
			out=1;
		}
	}while( (cpts[i]!=1 || i!=0) && (out!=1) );
 
 
	return Combinations(lists, cpts, size);
}

Encore merci !