Discussion :

[ahmadou_20]

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 :

Code :

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

1
2
3
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.

[joel.drigo]

Salut,

Avant d'attaquer l'algorithme complètement récursif, tu peux peut-être réfléchir à une version partiellement récursive. Déjà, commencer à découper le problème en trois parties : la partie clef Integer peut être séparée (toutes les listes résultants commence par la clef), l'aspect pas de caractères en commun (qui peut se traiter à part, par test), et la création des combinaisons.

Ensuite, une bonne méthode (à mon avis) pour faire un algorithme, c'est de le "jouer" sur papier d'abord, donc d'analyser la forme de différents résultats et les variations et répétions : on voit rapidement qu'il y a une notion de sous liste (ce qui fait tout de suite penser à List.sublist()) qui se dégage (chaque sous partie du résultat est le premier élément d'une liste, suivi des combinaisons de la sous-liste suivant ce premier élément.

En gros, à partir de [AB, BC, CD] :
[AB]
[AB, BC]
[AB, BC, CD]
...
[AB, CD]
...
[BC]
[BC, CD]
...

• c'est [AB] le premier dans [AB, BC, CD]
  
  • suivi de [BC] le suivant de [AB], dans [AB, BC, CD] (donc le premier de la sous liste [BC, CD], la sous liste de 1 à fin)
    
    • suivi de [CD] le suivant de [BC], dans [BC, CD] (donc le premier de [CD], la sous liste de 1 à fin)
    • ...
  
  
  • suivi de [CD] le suivant de [BC], dans [BC, CD], donc le premier de [CD]
  • ...
• c'est [BC] le premier dans [BC, CD] ...
  
  • suivi de [CD] le suivant de [BC], dans [BC, CD], etc.
  • ...

L'algorithme devient simple (ici c'est le résultat final complètement récursive : en partiellement récursif, j'avais des boucles pour créer les sous-listes, qu'il a été facilement de transformer en appel récursif) :

• list : liste de String en entrée
• results : liste pour collecter les résultats (sortie) (une List<List<String>> en Java)
• stack : une pile, pour construire récursivement les résultats (java.util.Stack en Java)

Code pseudocode :

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
 
creer tous(results, stack, list) {
    appeler creer(results, stack, list);
    si list n'est pas vide
    alors appeler create tous (results, stack, sous liste de list de 1 à fin)
    sinon results.add( liste vide ) // cas aucun élement, qu'on pourrait traiter complètement à part
}
 
creer(results, stack, list) {
    si list n'est pas vide
       item0 = premier élément de list
       // si il n'y a pas de caractère en commun entre item0 et un élément de stack 
          empile item0 dans stack
          stocke dans results une copie de stack // java: results.add(new ArrayList<>(stack)));
          appeler creer Sous-Liste( results, stack, sous liste de list de 1 à fin )
          dépile item0 de stack
      // fin si
   fin si
}
 
creer Sous-Liste(results, stack, list) {
     appeler creer(results, stack, list);
     si list pas vide
     alors appeler creer Sous-Liste(results, stack, sous liste de list de 1 à fin);
}

EDIT: en relisant, mon pseudocode, je me suis aperçu qu'il pouvait il y avoir une ambiguité (non ambigu en Java) : par "sous liste de list de 1 à fin", il faut traduire en java par list.sublist(1, list.size()); (j'aurais dû écrire "sous liste du deuxième élement à fin"

[ahmadou_20]

Merci de ta réponse.

je commence a voir un peu comment le probleme doit etre adresse.

Sauf que je suis pas sur d avoir tres bien compris la structure du code car ton pseudo code tu passes toutes les variables qu elles soient en entree ou en sortie comme arguments d entree a toutes les methodes que tu as creees (creer, creer tous, creer Sous_Liste).

je peux avoir stp davantage d explications ?

Merci d avance encore une fois !!!

[joel.drigo]

On peut écrire une méthode comme ça :

Code :

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

1
2
3
4
public List<String> create() {
      List<String> list = new ArrayList<>();
      list.add("truc");
}

ou on peut écrire :

Code :

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

1
2
3
public void create(List<String> list) {
      list.add("truc");
}

que l'on appelle par :

Code :

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

create(new ArrayList<>());

L'avantage ici c'est de créer qu'une seule instance de ArrayList, que l'on remplit dans les différents appels récursif.

On pourrait écrire :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<String> create() {
      List<String> list = new ArrayList<>();
      list.addAll(createSubList(...));
}
 
public List<String> createSubLists(...) {
      List<String> list = new ArrayList<>();
      list.add(...);
      list.add(...);
      ...
      list.addAll(createSubLists(...);
      return list;
}

Mais tu vois qu'on créée ici une nouvelle ArrayList à chaque récursion.

Le début du code de la méthode finale de détermination des combinaisons peut s'écrire donc :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
public List<List<String>> create(List<String> list) {
    List<List<String>> results=new ArrayList<>();
    create(results, list);
    return results;
}
 
private void create(List<List<String>> results, List<String> list) {
 
    Stack<String> stack = new Stack<String>();
    createAll(results, stack, list);
 
}

où createAll correspond à "créer tous" dans le pseudo-code.

[ahmadou_20]

D accord.

mais je ne vois pas l equivalent de creer Sous_Liste dans le code de la methode finale que tu m as filé ?

On ne l utilisera plus ?

Merci.

[joel.drigo]

Non, mais je ne t'ai pas mis tout le code non plus. Je vais pas de mâcher tout le travail : tu remarqueras que dans la méthode private, il y a un appel à createAll dont je n'ai pas mis le code : il ne reste plus qu'à coder l'algo en trois méthodes conformément au pseudo code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
private void createAll(List<List<String>> results, Stack<String> stack,
		List<String> list) {
}
 
private void create(List<List<String>> results,
		Stack<String> stack, List<String> list) {
}
 
private void createSubLists(List<List<String>> results,
		Stack<String> stack, List<String> subList) {
}