Bonjour, je vous présente mon problème, soit une HashMap<String,ArrayList<String>>, je dois calculer toutes les ensembles possibles pour toutes les key.

En exemple, si toutes les keys forment cette ensemble E = {A,B,C,D,E}, je pense qu'il faudrait avoir une ArrayList<ArrayList<String>> qui contient les solutions par exemple (A),(A,B),(A,B,C),(A,B,C,D),(A,B,C,D,E),(A,C),(A,C,D),(A,C,E) etc...

J'ai longuement réfléchi a comment implémenter cet algorithme mais je n'ai pas réussi je ne possède aucune piste même après des recherches sur internet.

Merci d'avance pour votre aide.

-
Edité par JorjeAmbino 16 décembre 2022 à 3:22:28

> je ne possède aucune piste même après des recherches sur internet.

C'est pourtant un exercice très classique : énumérer les parties d'un ensemble (fini).

> je pense qu'il faudrait avoir une ArrayList<ArrayList<String>>

C'est bien de penser, mais Il n'est absolument pas obligatoire de produire un objet contenant toutes les parties. On peut aussi produire un itérateur qui les fournira une par une à la demande. Ou une fonction qui produit une des 2^N parties.

package javaapplication7;

import java.util.ArrayList;
import java.util.List;


public class JavaApplication7 {

    
    public static <T> ArrayList<T> n_ieme_partie(int numero, List<T> liste) {
        var resultat = new ArrayList<T>();
        for (var element : liste ) {
            if (numero % 2 == 1) {
                resultat.add(element);
            }
            numero = numero / 2;
        }
        return resultat;
    }
    public static void main(String[] args) {
        final var liste = List.of( "zero", "un", "deux");
        System.out.format("%s\n", liste);
        int nb_parties = 1 << liste.size();
        for (int numero = 0; numero < nb_parties; numero++) {
            System.out.format("%d\t%s\n", 
                    numero, n_ieme_partie(numero, liste));
        }
    }
    
}

Execution

[zero, un, deux]
0	[]
1	[zero]
2	[un]
3	[zero, un]
4	[deux]
5	[zero, deux]
6	[un, deux]
7	[zero, un, deux]

Explication de la magie : chacun des bits du numéro correspond à un élément de la liste. Quand le bit est 1, on met l'élément dans le résultat.

----

Sinon, on peut jouer avec les Streams, si on a une boite d'aspirine à proximité

     parties_de(liste).forEach(
                partie -> System.out.format("-> %s\n", partie)
        );

affiche

-> []
-> [deux]
-> [un]
-> [deux, un]
-> [zero]
-> [deux, zero]
-> [un, zero]
-> [deux, un, zero]

avec

    public static <T> Stream<List<T>> parties_de(List<T> liste) {
        return parties_de(liste, 0);
    }

    private static <T> Stream<List<T>> parties_de(List<T> liste, int debut) {
        if (debut >= liste.size()) {
            // fournit la partie vide
            return Stream.of( new ArrayList<>());
        } else {
            final var premier = liste.get(debut);
            return Stream.concat(
                    parties_de(liste, debut + 1),
                    parties_de(liste, debut + 1).map(partie -> {
                        partie.add(premier);
                        return partie;
                    }));
        }
    }

(La seconde fonction fournit les parties de la sous-liste qui commence à l'indice début).

Ou alors on peut écrire la fonction comme ceci

    private static <T> Stream<List<T>> parties_de(List<T> liste, int debut) {
        if (debut >= liste.size()) {
            // fournit la partie vide
            return Stream.of( new ArrayList<>());
        } else {
            final var premier = liste.get(debut);
            return parties_de(liste, debut+1).flatMap((List<T> p) -> {
                var p2 = new ArrayList<T>();
                p2.add(premier);
                p2.addAll(p);
                return Stream.of(p, p2);
            });
        }
    }

pour avoir les parties en respectant l'ordre des éléments

-> []
-> [zero]
-> [un]
-> [zero, un]
-> [deux]
-> [zero, deux]
-> [un, deux]
-> [zero, un, deux]

-
Edité par michelbillaud 17 décembre 2022 à 23:06:41

Je ne connais pas suffisamment le Java. Je vous donne mon code en C++. Désolé.
Ça devrait pouvoir se traduire facilement en Java.
Les combinaisons sont affichées en ordre lexicographiques.
J'utilise un "compteur kilométrique" ou "compteurcirculaire" modifié.
-
#include <iostream>
#include <string>
#include <vector>
 
int main(void) {
    std::string chaine = {"abcde"};
    std::vector<int> indice (chaine.size());
    std::string suite = {""};
 
    std::cout << "''" << std::endl;
 
    int longueur = chaine.size();
    int i = 0;
    int v = 0;
    while(i >= 0) {
        while(i < longueur && v < longueur) {
            indice[i] = v;
            suite += chaine[indice[i]];
            std::cout << "'" << suite << "'" << std::endl;
            i++;   v++;
        }
        i--;
        suite.pop_back();
        if(i>=0) v = indice[i] + 1;
    }
}

Pour calculer tous les ensembles possibles pour toutes les clés d'une HashMap <String, ArrayList <String>>, vous pouvez utiliser la méthode keySet() de la classe HashMap pour obtenir un ensemble de toutes les clés de la HashMap. Vous pouvez ensuite parcourir cet ensemble de clés et utiliser la méthode get() de la HashMap pour obtenir l'ArrayList associé à chaque clé. Vous pouvez utiliser cette ArrayList pour générer tous les ensembles possibles en utilisant une approche récursive.

Voici un exemple de code qui montre comment faire cela:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;

public class Main {
  public static void main(String[] args) {
    // Créez une HashMap avec quelques données de test
    HashMap<String, ArrayList<String>> map = new HashMap<>();
    ArrayList<String> list1 = new ArrayList<>();
    list1.add("A");
    list1.add("B");
    list1.add("C");
    map.put("Key1", list1);
    ArrayList<String> list2 = new ArrayList<>();
    list2.add("D");
    list2.add("E");
    map.put("Key2", list2);
    ArrayList<String> list3 = new ArrayList<>();
    list3.add("F");
    list3.add("G");
    list3.add("H");
    list3.add("I");
    map.put("Key3", list3);

    // Obtenez un ensemble de toutes les clés de la HashMap
    Set<String> keys = map.keySet();

    // Parcourez l'ensemble de clés et utilisez la méthode get pour obtenir l'ArrayList associé à chaque clé
    for (String key : keys) {
      ArrayList<String> values = map.get(key);
      System.out.println("Ensembles possibles pour la clé " + key + ":");
      // Appelez la méthode recursive pour générer tous les ensembles possibles à partir de l'ArrayList
      generateSets(values);
    }
  }

  public static void generateSets(ArrayList<String> values) {
    // Si l'ArrayList est vide, imprimez un ensemble vide
    if (values.size() == 0) {
      System.out.println("[]");
      return;
    }
    // Sinon, générez tous les ensembles possibles à l'aide d'une approche récursive
    for (int i = 0; i < values.size(); i++) {
      // Prenez l'élément courant
      String element = values.get(i);
      // Créez une nouvelle ArrayList sans l'élément courant
      ArrayList<String> remainingElements = new ArrayList (values);
remainingElements.remove(i);
// Appelez récursivement la méthode avec la nouvelle ArrayList
generateSets(remainingElements);
// Imprimez l'ensemble avec l'élément courant
System.out.println("[" + element + "]");
}
}
}

Ce code imprimera tous les ensembles possibles pour chaque clé de la HashMap. Notez que cette approche peut être assez coûteuse en termes de temps de calcul et de mémoire si les ArrayList associées à chaque clé sont très longues, car elle génère tous les ensembles possibles pour chaque ArrayList.

Voici quelques façons d'optimiser le code ci-dessus pour le rendre plus efficace en termes de temps de calcul et de mémoire:

1. Utilisez une approche itérative plutôt qu'une approche récursive: l'approche récursive utilisée dans le code ci-dessus peut être coûteuse en termes de temps de calcul et de mémoire, car elle génère tous les ensembles possibles pour chaque ArrayList. Vous pouvez remplacer l'approche récursive par une approche itérative en utilisant une boucle for pour parcourir chaque élément de l'ArrayList et en générant tous les ensembles possibles en combinant chaque élément avec les ensembles générés précédemment. Cela devrait être plus rapide et utiliser moins de mémoire.

2. Utilisez une structure de données plus efficace pour stocker les ensembles générés: au lieu d'utiliser une ArrayList pour stocker les ensembles générés, vous pouvez utiliser une structure de données plus efficace, comme une liste chainée ou un tableau. Cela devrait être plus rapide et utiliser moins de mémoire, surtout si vous avez de grandes ArrayList à traiter.

3. Ne stockez que les ensembles uniques: si vous n'avez pas besoin de stocker les ensembles en double, vous pouvez utiliser une structure de données qui ne permet pas les doublons, comme un ensemble (Set) ou un dictionnaire (Map). Cela devrait être plus rapide et utiliser moins de mémoire, car vous n'aurez pas à vérifier si un ensemble est déjà présent dans la structure de données.

4. Utilisez une HashMap pour stocker les ensembles générés: au lieu d'utiliser une ArrayList ou une autre structure de données pour stocker les ensembles générés, vous pouvez utiliser une HashMap. Cela devrait être plus rapide et utiliser moins de mémoire, car la HashMap a une complexité d'accès en temps constant en moyenne.

-
Edité par AdrianaPetrovski 31 décembre 2022 à 14:27:12