Slt,
 
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.

Salut

La recursivite marche toujours de la meme maniere, ton probleme c'est probablement plutot un probleme d'algorithmie qu'un probleme de Java.
Tu ne dis pas ce que t'as essaye et ou tu bloques donc c'est dur de t'aider "utilement" (essayer de te faire realiser a quel endroit tu as une erreur de raisonnement par exemple).
Bon vu que ca ne ressemble pas trop a de l'aide au devoir, je vais tenter une reponse quand meme... si c'en est, tant pis pour moi

Implementer un algo recursif c'est generalement tres simple tant que c'est fait rigoureusement.

Les questions de base sont:
1 - A une etape donnee de ton algo, tu as besoin de quoi pour pouvoir avancer? -> La reponse a ca va constituer les parametres d'entree de ta fonction recursive
2 - Que retourne chaque etape? -> La reponse a ca va constituer la valeur de retour de ta fonction recursive

Il y a plusieurs facons de faire selon ce que tu vas repondre aux questions, mais par exemple:
1 - Tu as besoin de:
-> la liste des elements (ta variable "list" ), evidemment
-> a quel indice de la liste tu en es, histoire de ne pas t'embeter avec les elements que tu as deja utilises, et aussi de savoir quand t'arreter
-> la liste des elements que tu as deja inclus dans ton resultat en cours, pour pouvoir verifier les chevauchements

2 - Ca retourne:
-> une liste de liste d'elements qui ne chevauchent pas les elements deja inclus

De ca, tu deduis la declaration de ta fonction:

Ensuite, une fonction recursive "de base", c'est toujours du IF <condition de fin> THEN RETURN <resultat "aux bornes"> ELSE <traitement recursif>
Ici ta condition de fin est simple: si tu as atteint la fin de ta liste d'elements, et donc que ton parametre indice "depasse" de ta liste d'elements.

Maintenant, faut ecrire le traitement recursif. Mettons la generation du "1" de tes listes de cote, on s'en fout un peu au fond, c'est juste un detail. L'indice en parametre de ta fonction indique de quel element on s'occupe. Imagines que tu sois au tout debut: l'indice est a 0.

- Deja, tu initialises une liste vide, qui va contenir le resultat.

- Tu regardes l'element que tu as a l'indice 0: "AB". Est-ce qu'il chevauche un element deja inclus? Non, puisque tu n'as aucun element deja inclus pour le moment. Du coup:
        - tu dois l'ajouter a ta liste de resultats (i.e le resultat "final" [1,AB])
        - toute chaine commencant par "AB" doit egalement etre ajoutee a la liste de resultats. Comment obtenir ces chaines? C'est la que la recursivite intervient: il faut rappeler ta fonction, maintenant pour l'indice 1, en indiquant que tu as deja "AB" de inclus. Donc tu ajoutes "AB" a elementsDejaInclus et tu appelles "maFonctionRecursive(elements, indice+1, elementsDejaInclus)". Tu sais que cet appel va te renvoyer toutes les chaines possibles en considerant que "AB" est deja inclus. De la, tu prends chacune de ces chaines, tu y ajoutes "AB" au debut, et tu les ajoutes au resultat "final". Ca va ajouter [1,AB,CD] , [1,AB,CD,EF] , [1,AB,CD,FG] , [1,AB,DE] , [1,AB,DE,FG] , [1,AB,EF] et [1,AB,FG] a ton resultat.
        - Maintenant que tu as parcouru tout le "cote" "j'inclus AB", il faut le retirer de elementsDejaInclus pour ne pas "tromper" l'algo plus tard.

- Quid du reste des resultats de ton exemple, ceux ne commencant pas par AB? Facile: tu viens de faire une recursivite en considerant que tu "prenais" "AB". Ben maintenant, tu fais la meme en considerant que tu ne prends pas "AB". Tu as deja enleve "AB" de elementsDejaInclus au-dessus, donc tu peux rappeler "maFonctionRecursive(elements, indice+1, elementsDejaInclus)" une seconde fois; cette fois, ca te retourne toutes les chaines ne commencant pas par "AB"; tu peux les ajouter directement a ta liste de resultats. ([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])

- Et voila, c'est tout, tu retournes le resultat et c'est fini.

Le "traitement recursif" final va donc ressembler a ca (a toi de "traduire" en Java):

Et comme dit au debut, c'est une solution possible parmi d'autres. Probablement pas la plus performante, ni la plus "jolie", etc.

 
A noter : la JVM ne supporte pas le TCO, donc selon la profondeur de ton traitement tu t'exposes à une explosion de la stack.