Comment puis-je calculer efficacement le Powerset d'un ensemble en Java ?

Comprendre le Powerset en Java

Le Powerset d'un ensemble représente tous les sous-ensembles possibles de ses éléments, y compris l'ensemble vide et l'ensemble d'origine lui-même. Pour un ensemble contenant n éléments, son ensemble de puissances est constitué de 2^n sous-ensembles uniques.

Obtenir le Powerset efficacement

En Java, on peut définir une fonction getPowerset qui calcule l'ensemble des puissances d'un ensemble donné. La complexité temporelle optimale pour cette opération est O(2^n), où n est le nombre d'éléments dans l'ensemble d'entrée.

Implémentation utilisant les génériques et la récursion

L'implémentation suivante exploite les génériques pour fonctionner avec des ensembles de tout type :

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<>();
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<>());
        return sets;
    }
    List<T> list = new ArrayList<>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<>(list.subList(1, list.size()));
    for (Set<T> set : powerSet(rest)) {
        Set<T> newSet = new HashSet<>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }
    return sets;
}

Utilisation et Exemple

Pour utiliser cette fonction, instanciez un ensemble et transmettez-le comme argument à getPowerset. Par exemple, avec votre exemple d'entrée :

Set<Integer> mySet = new HashSet<>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set<Integer> s : powerSet(mySet)) {
    System.out.println(s);
}

Cela imprimera l'ensemble de puissances de l'ensemble donné dans le format attendu.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!