Générer une liste d'objets

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:

---

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 !

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:

---

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:

---

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:

---

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

Merci cela marche très bien ! :D

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

Code:

---

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:

---

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:

---

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:

---

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 !