Combinaisons de listes par récursivité

Version imprimable

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:

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

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

Code:

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]

03/12/2011, 15h11
Invité

Merci de ta réponse mais je ne comprend pas très bien le principe de ton programme ? :?
03/12/2011, 15h40
Steph_ng8

Arf... :aie:

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. ;)

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

Code:

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 !