Un algo récursif en java ?
Résolu
ahmadou_20
Messages postés
6
Statut
Membre
-
ahmadou_20 Messages postés 6 Statut Membre -
ahmadou_20 Messages postés 6 Statut Membre -
Bonjour,
Ca fait peu de temps que j ai commence à coder en Java et je me trouve un peu coincé là.
Le truc c est que je veux mettre en oeuvre un petit algo recursif pour resoudre le probleme presente ci dessous :
List<String> list = Arrays.asList("AB","BC","CD","DE","EF", "FG");
Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
map.put(1, list);
Je cherche du coup a stocker dans une liste toutes les combinaisons possibles qui commencent avec 1 (la cle de la map) et incluent les elements de list (la valeur de la map) qui ne se chevauchent pas (c est a dire qui ne partagent aucun caractere e.g. "AB" et "BC" se chevauchent car ils partagent le caractere B)
EXEMPLE DE RESULTAT AUQUEL J AIMERAIS ABOUTIR:
[1]
[1,AB] , [1,AB,CD] , [1,AB,CD,EF] , [1,AB,CD,FG] , [1,AB,DE] , [1,AB,DE,FG] , [1,AB,EF] , [1,AB,FG]
[1,BC] , [1,BC,DE], [1,BC,DE,FG] , [1,BC,EF] , [1,BC,FG]
[1,CD] , [1,CD,EF] , [1,CD,FG]
[1,DE] , [1,DE, FG]
[1,EF]
[1,FG]
J ai tout essaye mais j y arrive pas et je commence a desesperer un peu. AU SECOURS !!!!!!!!!
J aimerais bien utiliser la recursivite (pour avoir qlq chose d assez generique qui pourrait s appliquer a un cas beaucoup plus complexe).
Mais si vous pensez savoir qlq chose de plus simple, je sui preneur.
Merci de votre aide.
Ca fait peu de temps que j ai commence à coder en Java et je me trouve un peu coincé là.
Le truc c est que je veux mettre en oeuvre un petit algo recursif pour resoudre le probleme presente ci dessous :
List<String> list = Arrays.asList("AB","BC","CD","DE","EF", "FG");
Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
map.put(1, list);
Je cherche du coup a stocker dans une liste toutes les combinaisons possibles qui commencent avec 1 (la cle de la map) et incluent les elements de list (la valeur de la map) qui ne se chevauchent pas (c est a dire qui ne partagent aucun caractere e.g. "AB" et "BC" se chevauchent car ils partagent le caractere B)
EXEMPLE DE RESULTAT AUQUEL J AIMERAIS ABOUTIR:
[1]
[1,AB] , [1,AB,CD] , [1,AB,CD,EF] , [1,AB,CD,FG] , [1,AB,DE] , [1,AB,DE,FG] , [1,AB,EF] , [1,AB,FG]
[1,BC] , [1,BC,DE], [1,BC,DE,FG] , [1,BC,EF] , [1,BC,FG]
[1,CD] , [1,CD,EF] , [1,CD,FG]
[1,DE] , [1,DE, FG]
[1,EF]
[1,FG]
J ai tout essaye mais j y arrive pas et je commence a desesperer un peu. AU SECOURS !!!!!!!!!
J aimerais bien utiliser la recursivite (pour avoir qlq chose d assez generique qui pourrait s appliquer a un cas beaucoup plus complexe).
Mais si vous pensez savoir qlq chose de plus simple, je sui preneur.
Merci de votre aide.
4 réponses
-
Bonjour,
À quoi sert ton 1 ?
J'ai fait un code il y a quelques temps Énumérer un ensemble comme si on avait des boucles imbriquées. Je ne me souviens plus trop du code, mais ça doit être majoritairement itératif avec peut être un peu de récursivité de temps en temps, mais en tout ça c'est suffisamment générique pour tes besoins.
Exemple :
public static void main(String[] args) { List<String> list = Arrays.asList("AB","BC","CD","DE","EF","FG"); int sz = list.size(); for (long[] tab : new Enumeration(sz, 0, 1, 0, false)) { for (int i=0; i<sz; i++) if (tab[i]==0) System.out.print(list.get(i)+" "); System.out.println(); } }
Cela affiche toutes les combinaisons possibles :
AB BC CD DE EF FG
AB BC CD DE EF
AB BC CD DE FG
AB BC CD DE
AB BC CD EF FG
AB BC CD EF
AB BC CD FG
AB BC CD
AB BC DE EF FG
AB BC DE EF
...
Il faudra juste que tu élimines les cas de conflits que tu ne veux pas.
La confiance n'exclut pas le contrôle-
Remarque : dans ton cas très particulier, on peut même se passer de mon code.
Voici une manière directe de faire (limitée à 63 éléments dans la liste).
Alors c'est itératif, mais la récursivité ne servirait pas à grand chose ici.
public static void main(String[] args) { List<String> list = Arrays.asList("AB","BC","CD","DE","EF","FG"); int sz = list.size(); double pow = Math.pow(2, sz); if (pow>Long.MAX_VALUE) throw new RuntimeException("list with "+sz+" elements is too large"); for (long n=0, m=(long) pow; n<m; n++) { for (long i=0, c=n; i<sz; i++, c/=2) if (c%2==0) System.out.print(list.get((int) i)+" "); System.out.println(); } }
-
-
Merci énormément.
Ca a l'air de bien marcher.
J'ai réussi à éliminer toutes les listes là ou il y des conflits. Mais je l'ai fait en aval (après le code que tu m as filé).
Je me demandais si il y a un moyen de faire cela au sein meme de ton code mais pour le moment j ai pas reussi a le faire.
Je t ai mis tout le code (le tien + celui que j ai rajoute pour eliminer les conflits) :
List<String> list = Arrays.asList("A-B","B-C","C-D","D-E","E-F","F-G");
int sz = list.size();
List<List<String>> listeTotale = new ArrayList<>();
double pow = Math.pow(2, sz);
if (pow>Long.MAX_VALUE)
throw new RuntimeException("list with "+sz+" elements is too large");
for (long n=0, m=(long) pow; n<m; n++)
{
List<String> liste = new ArrayList<>();
for (long i=0, c=n; i<sz; i++, c/=2){
if (c%2==0){
//System.out.print(list.get((int) i)+" ");
liste.add(list.get((int) i));
}
}
listeTotale.add(liste);
}
System.out.println("Liste Totale");
for(List<String> ls : listeTotale){
System.out.println(ls);
}
System.out.println("Liste Totale size " + listeTotale.size());
System.out.println("\n \n*********Liste Finale (sans conflits)*********");
List<List<String>> result = new ArrayList<>();
//Elimination des conflits
for(List<String> ls : listeTotale){
if(!ls.isEmpty()){
int index=0;
boolean conflict = false;
String previousItem = "";
String nextItem = "";
while(!conflict && index < ls.size()-1){
previousItem = ls.get(index);
nextItem = ls.get(index+1);
Set<String> set = new HashSet<>(Arrays.asList(previousItem.split("-")));
set.retainAll(Arrays.asList(nextItem.split("-")));
if(!set.isEmpty()) {
conflict = true;
}
index++;
}
if(!conflict){
result.add(ls);
}
}
}
for(List<String> res : result){
System.out.println(res);
}
System.out.println("Liste Finale size " + result.size());
Merci encore une fois.-
Il vaut toujours mieux filtrer au plus tôt, parce que sinon tu vas te retrouver avec une liste de 2^sz éléments qui prendra beaucoup de place en mémoire alors que la plupart des éléments sont voués à disparaître. D'ailleurs si le but est d'afficher les résultats, il vaut mieux alors les afficher dès qu'on les sait correct, plutôt que de les stocker en mémoire et ne les afficher qu'à la fin...
List<String> list = Arrays.asList("AB", "BC", "CD", "DE", "EF", "FG"); //List<List<String>> res = new ArrayList<>(); int sz = list.size(); double pow = Math.pow(2, sz); if (pow > Long.MAX_VALUE) throw new RuntimeException("list with " + sz + " elements is too large"); main: for (long n = 0, m = (long) pow; n < m; n++ ) { List<String> item = new ArrayList<>(); Set<Character> set = new TreeSet<Character>(); for (long i = 0, j = n; i < sz; i++ , j /= 2) { if (j % 2 == 1) { String str = list.get((int) i); for (int k = 0; k < str.length(); k++ ) if ( !set.add(str.charAt(k))) continue main; item.add(str); } } if ( !item.isEmpty()) { //res.add(item); System.out.println(item); } } /* for (List<String> item : res) System.out.println(item); //*/
-
-
Merci bcp.
Sauf que il y a une petite chose que je n arrive pas a comprendre. (d ailleurs c est la premiere fois que je la vois).
main: for (long n = 0, m = (long) pow; n < m; n++ )
et puis
continue main ???
Plus de détails peut etre stp concerant la label main que tu utilises ici ?
Merci.-
Quand on fais
for (...) continue;
cela passe à l'itération suivante mais pour la boucle courante, or ici on a plusieurs boucles imbriquées, donc si je faisais uncontinue
simple, je poursuivrais la bouclefor (int k
alors que moi c'est la bouclefor (long n
que je veux continuer, en zappant la fin des bouclesfor (long i
etfor (int k
.
J'ai donc mis un label à la boucle qui m'intéressait et spécifié le même label au continue de sorte à bien aller où je voulais.
Remarque : on peut faire pareil avec lebreak
, ainsi qu'avec les boucleswhile
.
-
-
D accord.
c est compris.
merci beaucoup de ton aide.
A la prochaine :).
