Discussion :

[Thadeana]

Bonsoir,

Je cherche à générer des sous ensembles d'un ensemble fini d'Arete (objet). Ceci est dans le but d'étudier chaque sous-ensemble par la suite. En fouinant un peu j'ai trouvé cet algorithme récursif :

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
30
31
32
33
public static Stack<String> combination(Stack<Character> characters) {
	Stack<String> result = new Stack<String>();
 
	// la liste des carateres est vide => resultat vide
	if (characters.isEmpty()) return result;
 
	// retire le 1er caractere le la liste
	Character first = characters.remove(0);
 
	// calcule les sous-combinaisons avec les caracteres restants
	Stack<String> subcombination = combination(characters);
 
	// ajoute: le caractere seul
	result.add(first.toString());
 
	// ajoute: le caractere seul devant chaque sous-combinaison
	for(String s:subcombination)
		result.add(first+s);
 
	// ajoute: les sous-combinaisons
	result.addAll(subcombination);
 
	return result;
}
 
public static void main(String[] args) {
	Stack<Character> stack = new Stack<Character>();
	stack.push('A'); stack.push('B'); stack.push('C');
 
	Stack<String> resultats = combination(stack);
	for(String s:resultats)
		System.out.println(s);
}

Le problème c'est qu'il est fait avec des caractères. Je bloque principalement à cette ligne // ajoute: le caractere seul devant chaque sous-combinaison
for(String s:subcombination)
result.add(first+s);

Je n'arrive pas à obtenir par exemple : [12, 23, 53, 14] un sous-ensemble où chaque chiffre correspond aux sommets de l'arête. Merci d'avance !

[joel.drigo]

Salut,

Le code que tu as trouvé utilise une sorte d'astuce : en entrée on a une collection de caractères, et en sortie une liste de chaînes de caractères, qui est une sorte de collection de caractères. Dans le cas d'autre chose que caractères, on a pas ce type chaîne de... Il faut donc déjà simplement remplacer les String par des collections de machin et passer une collection de machin en entrée (dans ton cas machin c'est Arête);

En revanche, il est complètement abscons d'utilier une pile (lifo) ici, d'autant qu'on utilise même pas les possibilités spécifiques de la lifo (on fait des push, mais on pourrait les rempalcer par des add, et des addAll - aucun pop en tout cas). Peut-être que c'est dans le but de gain de performance sur le remove() du premier élément, mais le fait que la Stack soit synchronisée et qu'on en créé une à chaque récursion fait que ce n'est pas une bonne idée.

Ensuite, il faut savoir que ce programme ne génère pas exactement toutes les combinaisons, mais les combinaisons distinctes en négligeant l'ordre. Par exemple, pour A, B, C, on va obtenir A, AB, ABC, AC, B, BC, C. Mais si c'est ce que tu cherches à obtenir, l'algorithme sous-jascent n'est pas si mauvais, il suffit donc de modifier ce programme :

• Utiliser des List au lieu de Stack
• Utiliser des List<Character> au lieu de String
• Au lieu de faire remove(0) pour séparer le caractère courant du reste,
  
  • utiliser un simple index qu'on incréement à chaque récursion (le premier caractère est celui là position index, le reste, ce qu'il y a après, qui va se traiter naturellement avec la récursion)
  • ou utilise sublist(1) pour traiter à chaque fois la suite de la liste, et get(0) pour récupérer le premier
  • Ensuite au lieu de créer des chaines par concaténation, on créer des listes par copie
  
  

Ce qui donne :

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
30
31
32
33
34
35
36
37
public static List<List<Character>> combination(List<Character> characters) { 
 
		// la liste des carateres est vide => resultat vide
		if (characters.isEmpty()) return Collections.emptyList(); 
 
		final List<List<Character>> result = new ArrayList<>();
 
		// calcule les sous-combinaisons avec les caracteres restants
		final List<List<Character>> subResults = combination(characters.subList(1, characters.size())); 
 
		// la liste avec le caractère actuel
		final List<Character> list = Arrays.asList(characters.get(0)); 
 
		// ajoute: le caractere seul
		result.add(list);
 
		// ajoute: le caractere seul devant chaque sous-combinaison
		for(List<Character> subResult : subResults) {
			List<Character> newResult = new ArrayList<>(list);
			newResult.addAll(subResult);
			result.add(newResult);
		}
 
		// on ajoute toutes les combinaisons trouvées dans l'appel récursif
		result.addAll(subResults);
 
		return result;
 
	}
 
	public static void main(String[] args) {
 
 
		List<List<Character>> resultats = combination(Arrays.asList('A','B','C'));
		for(List<Character> s:resultats)
			System.out.println(s);
	}

Ensuite, on peut rendre paramétrable le type (c'est quasiment un chercher/remplacer) :

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
30
31
32
33
34
35
36
37
	public static <T> List<List<T>> combination(List<T> characters) { 
 
		// la liste des carateres est vide => resultat vide
		if (characters.isEmpty()) return Collections.emptyList(); 
 
		final List<List<T>> result = new ArrayList<>();
 
		// calcule les sous-combinaisons avec les caracteres restants
		final List<List<T>> subResults = combination(characters.subList(1, characters.size())); 
 
		// la liste avec le caractère actuel
		final List<T> list = Arrays.asList(characters.get(0)); 
 
		// ajoute: le caractere seul
		result.add(list);
 
		// ajoute: le caractere seul devant chaque sous-combinaison
		for(List<T> subResult : subResults) {
			List<T> newResult = new ArrayList<>(list);
			newResult.addAll(subResult);
			result.add(newResult);
		}
 
		// on ajoute toutes les combinaisons trouvées dans l'appel récursif
		result.addAll(subResults);
 
		return result;
 
	}
 
	public static void main(String[] args) {
 
 
		List<List<Character>> resultats = combination(Arrays.asList('A','B','C'));
		for(List<Character> s:resultats)
			System.out.println(s);
	}

Tu peux écrire maintenant :

Code :

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

1
2
3
4
5
6
7
	public static void main(String[] args) {
 
 
		List<List<Integer>> resultats = combination(Arrays.asList(1,2,3));
		for(List<Integer> s:resultats)
			System.out.println(s);
	}

Ou utiliser ton type Arete à la place de Character ou Integer, ou tout autre (il faudra juste veiller à ce que la méthode toString() soit implémentée ou adapter l'affichage à la fin, si nécessaire).

[Thadeana]

Merci cela marche très bien !

J'ai réussi à afficher avec ma List avec ce code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 public static void affichage_enumeration(List<List<Arete>> resultats) {
    	System.out.println("Affichage des sous-ensembles");
    	for(int i = 0; i < resultats.size(); i++) {
        	List<final_test.Arete> test= resultats.get(i);
        	for(int j = 0; j < test.size(); j++) {
        		Arete a1 = test.get(j);
        		System.out.println(a1.d+" "+a1.g+" "+a1.p);	
        	}
        	System.out.println("____________________________");
         }
    	System.out.println("Fin de l'affichage des sous-ensembles");
    }

Par contre j'essaye aussi d'afficher une autre list du même type :

Code :

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

static List<List<Arete>> arbres = new LinkedList <List<Arete>>();

qui contient 7 éléments d'après le size() mais cela ne marche pas. Il y a que la partie

Code :

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

System.out.println("____________________________");

qui s'affiche. Je sais que le problème vient au niveau du clear() mais je ne vois pas comment le résoudre. J'ai besoin que ma liste se remette à 0 pour accueillir une autre liste d'arête à chaque parcours.

Je mets le code du remplissage de ma List<List<Arete>> au cas où ...

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
 public static List<List<Arete>> test_arbres(List<List<Arete>> resultats, List<Arete> arbre, int []a ) {
    	int compteur = 0;
    	for(int i = 0; i < resultats.size(); i++) { // voir pour tout les sous-ensemble
    		System.out.println("resultats");
    		System.out.println(resultats.size());
    		List<Arete> test = resultats.get(i);
    	    init(a); 
    		for (int j = 0; j < test.size(); j++ ){ // pour chaque sous-ensemble 
    			Arete a1 = test.get(j);
    			if (cyclep(a,a1.g,a1.d)) { // si ex premier sommet de l'arête à l'indice 0 ne force pas un cycle avec sommet d 
    				arbre.add(a1);  
    			}
 
    		}
    		System.out.println("Nous sortons du for");
    		System.out.println(arbre.size());
    		arbres.add(arbre);
    		arbre.clear();
    		compteur++;
    	}
    	System.out.println("le nombre d'arbres est "+compteur);
    	System.out.println("elements dans arbres "+ arbres.size());
 
    	return arbres;
    }

Un grand merci pour l'aide !