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

Calcul de Powerset pour les ensembles en Java

En informatique, l'ensemble de puissances d'un ensemble représente la collection de tous les sous-ensembles possibles de cet ensemble. Cet article explore comment construire l'ensemble de puissances d'un ensemble d'entiers en Java, en s'efforçant d'obtenir une complexité temporelle optimale.

Énoncé du problème

Étant donné un ensemble d'entiers définis en Java , notre objectif est de créer une fonction, getPowerset, qui calcule l'ensemble de puissances. Nous visons à atteindre la meilleure complexité temporelle possible pour cette fonction.

Solution

La complexité temporelle du calcul de l'ensemble de puissances est en effet O(2^n), où n est la taille de l'ensemble d'origine. La fonction ci-dessous utilise des génériques et des ensembles pour implémenter efficacement le calcul de l'ensemble de puissance :

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;
}

Test

Le code suivant illustre la fonction avec un exemple d'entrée :

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

Sortie

La sortie du test, telle que fournie dans le question, affiche l'ensemble des puissances de {1, 2, 3} :

[]
[2]
[3]
[2, 3]
[1]
[1, 2]
[1, 3]
[1, 2, 3]

En implémentant la fonction getPowerset à l'aide de génériques et de récursivité, nous obtenons une complexité temporelle optimale de O(2^n) et une solution efficace pour calculer l'ensemble des puissances d'un ensemble en Java.

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!