Sujet Précédent Sujet Suivant

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
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.
A voir également:

4 réponses

Réponse 1 / 4
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
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
0
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 à 13:52
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();
    }
}
0
Réponse 2 / 4
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
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.
0
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
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);
//*/
0
Réponse 3 / 4
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
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.
0
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
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 un 
continue
simple, je poursuivrais la boucle 
for (int k
alors que moi c'est la boucle 
for (long n
que je veux continuer, en zappant la fin des boucles 
for (long i
et 
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
.
0
Réponse 4 / 4
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
D accord.

c est compris.

merci beaucoup de ton aide.


A la prochaine :).
0

Discussions similaires

Téléchargement de la Bible en français
Grande sÅ"ur -
Icarenna -

6 réponses
Trouver des jeux java pour portable.
aurel350 -
minitorse -

6 réponses
application JAVA sur telephone portable !!!!
julio -
lehon kabre -

43 réponses