Comment générer efficacement le Powerset d'un ensemble en Java ?

Trouver des ensembles de puissances en Java : une approche efficace

L'ensemble de puissances d'un ensemble englobe tous les sous-ensembles possibles de l'ensemble d'origine. Pour un ensemble de taille n, le Powerset contient 2 ^ n éléments. En Java, il est courant de gérer la création d'ensembles de pouvoirs à l'aide d'algorithmes efficaces.

Considérez l'exemple :

Set monSet = new HashSet<>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set> ; powerSet = getPowerset(mySet);

Avec cette configuration, la tâche consiste à concevoir la fonction getPowerset qui génère l'ensemble de puissances de mySet avec une complexité temporelle optimale.

Complexité temporelle optimale : O (2^n)

Comme mentionné, l'ensemble de pouvoirs contient 2^n éléments. Par conséquent, la génération de tous ces éléments nécessitera intrinsèquement une complexité temporelle O(2^n).

Implémentation

Le code suivant offre une implémentation générique et efficace :

public statique Définir> powerSet(Set 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;

}

Exemple

Utilisation de l'exemple fourni précédemment :

Définir mySet = new HashSet<>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set s : powerSet(mySet)) {

System.out.println(s);

}

La sortie sera :

{}
{1}
{2}
{1, 2}
{3}
{1, 3}
{2 , 3}
{1, 2, 3}

Cela démontre la création de l'ensemble de puissances de l'ensemble spécifié avec un temps O(2^n) complexité.

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!