Un algo récursif en java ?
Résolu/Fermé
ahmadou_20
Messages postés
6
Date d'inscription
dimanche 24 août 2014
Statut
Membre
Dernière intervention
22 décembre 2014
-
24 août 2014 à 12:44
ahmadou_20 Messages postés 6 Date d'inscription dimanche 24 août 2014 Statut Membre Dernière intervention 22 décembre 2014 - 24 août 2014 à 18:42
ahmadou_20 Messages postés 6 Date d'inscription dimanche 24 août 2014 Statut Membre Dernière intervention 22 décembre 2014 - 24 août 2014 à 18:42
A voir également:
- Un algo récursif en java ?
- Waptrick java football - Télécharger - Jeux vidéo
- Jeux java itel football - Télécharger - Jeux vidéo
- Java apk - Télécharger - Langages
- Waptrick java voiture - Télécharger - Jeux vidéo
- Java décompiler - Télécharger - Langages
4 réponses
KX
Messages postés
16755
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 février 2025
3 020
Modifié par KX le 24/08/2014 à 13:27
Modifié par KX le 24/08/2014 à 13:27
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 :
Cela affiche toutes les combinaisons possibles :
Il faudra juste que tu élimines les cas de conflits que tu ne veux pas.
La confiance n'exclut pas le contrôle
À 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
ahmadou_20
Messages postés
6
Date d'inscription
dimanche 24 août 2014
Statut
Membre
Dernière intervention
22 décembre 2014
24 août 2014 à 16:48
24 août 2014 à 16:48
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) :
Merci encore une fois.
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.
KX
Messages postés
16755
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 février 2025
3 020
24 août 2014 à 17:51
24 août 2014 à 17:51
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); //*/
ahmadou_20
Messages postés
6
Date d'inscription
dimanche 24 août 2014
Statut
Membre
Dernière intervention
22 décembre 2014
24 août 2014 à 18:17
24 août 2014 à 18:17
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.
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.
KX
Messages postés
16755
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 février 2025
3 020
24 août 2014 à 18:27
24 août 2014 à 18:27
Quand on fais
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 le
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 un
continuesimple, je poursuivrais la boucle
for (int kalors que moi c'est la boucle
for (long nque je veux continuer, en zappant la fin des boucles
for (long iet
for (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 le
break, ainsi qu'avec les boucles
while.
ahmadou_20
Messages postés
6
Date d'inscription
dimanche 24 août 2014
Statut
Membre
Dernière intervention
22 décembre 2014
24 août 2014 à 18:42
24 août 2014 à 18:42
D accord.
c est compris.
merci beaucoup de ton aide.
A la prochaine :).
c est compris.
merci beaucoup de ton aide.
A la prochaine :).
24 août 2014 à 13:52
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.