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

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

Barbara Streisand
Libérer: 2024-11-30 22:07:12
original
905 Les gens l'ont consulté

How to Efficiently Generate the Powerset of a Set in 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;
Copier après la connexion

}

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);
Copier après la connexion

}

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!

source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers articles par auteur
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal