Programme pour toutes les combinaisons possibles entre N ensemble de mi éléments.

Version imprimable

09/04/2015, 21h29
saimer

Programme pour toutes les combinaisons possibles entre N ensemble de mi éléments.

Bonjour,

j'ai N ensembles, chacun dispose de m éléments (m diffère d'un ensemble à l'autre).
Je cherche un programme qui fait toutes les combinaisons possibles entre les N ensembles en sélectionnant un élément de chaque ensemble.

Exemple:

Ens1={e11, e12}; Ens2={e21, e22, e23}; Ens3={e31, e32}.

Combinaison 1 : e11 e21 e31
Combinaison 2 : e11 e21 e32
Combinaison 3 : e11 e22 e31
Combinaison 4 : e11 e22 e32
Combinaison 5 : e11 e23 e31
Combinaison 6 : e11 e23 e32
....
Combinaison 12 : e12 e23 e32

Remerciements.

Salut,

Algorithme récursif :

Soit ensembles : la liste des ensembles à combiner (ENTRÉE)

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


créerCombinaisons(ensembles) {

    créer combinaisons, une liste de combinaisons à produire, vide pour l'instant (SORTIE)
    créer construction, une liste d'éléments, vide, pour construire chaque combinaison
    
    appeler créerCombinaisons( combinaisons, construction, ensembles, 0); // index à 0 au début soit le premier ensemble

    retourner combinaisons // retourner le résultat en SORTIE

}

créerCombinaisons(combinaisons, construction, ensembles, index) {
		
      si index est supérieur ou égal à nombre d'ensembles alors
          stocker copie de construction actuel dans combinaisons
      sinon
          pour tous les élements E de l'ensemble d'index "index" dans ensembles faire 		
               ajouter E dans construction
               appeler récursivement creerCombinainons(combinaisons, construction, ensemble, index + 1) // traiter récursivement l'ensemble suivant
               supprimer E de construction (enlever le dernier élément actuel de construction)
          fin pour
      fin si
}

Citation:

Envoyé par joel.drigo

Salut,

Algorithme récursif :

Soit ensembles : la liste des ensembles à combiner (ENTRÉE)

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


créerCombinaisons(ensembles) {

    créer combinaisons, une liste de combinaisons à produire, vide pour l'instant (SORTIE)
    créer construction, une liste d'éléments, vide, pour construire chaque combinaison
    
    appeler créerCombinaisons( combinaisons, construction, ensembles, 0); // index à 0 au début soit le premier ensemble

    retourner combinaisons // retourner le résultat en SORTIE

}

créerCombinaisons(combinaisons, construction, ensembles, index) {
		
      si index est supérieur ou égal à nombre d'ensembles alors
          stocker copie de construction actuel dans combinaisons
      sinon
          pour tous les élements E de l'ensemble d'index "index" dans ensembles faire 		
               ajouter E dans construction
               appeler récursivement creerCombinainons(combinaisons, construction, ensemble, index + 1) // traiter récursivement l'ensemble suivant
               supprimer E de construction (enlever le dernier élément actuel de construction)
          fin pour
      fin si
}

Bonjour,

j'ai du mal à comprendre cet algorithme.

Puis-je avoir une idée plus détaillée.

je tiens à souligner que les ensembles sont des objets d'une classe C1 et les éléments sont d'une classe C2.

Merci.

Avec ce canevas, est-ce plus clair (C2 est String et C1 String[]) ?

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
public static void main(String[] args) {
 
		String[] ensemble1={"e11", "e12"}; 
		String[] ensemble2={"e21", "e22", "e23"};
		String[] ensemble3={"e31", "e32"};
 
		for(String[] combi : creerCombinaisons(ensemble1, ensemble2, ensemble3)) {
			System.out.println(Arrays.toString(combi));
		}
 
	}
 
	private static List<String[]> creerCombinaisons(String[]...ensembles) {
 
		List<String[]> combinaisons = new ArrayList<>();
		List<String> construction = new ArrayList<>();
		creerCombinaisons(combinaisons, construction, ensembles, 0);
		return combinaisons;
 
	}
 
	private static void creerCombinaisons(List<String[]> combinaisons, List<String> construction, String[][] ensembles, int index) {
 
               // code ici		
 
	}