Comment générer efficacement le Power Set d'un ensemble Java ?

Obtention du Powerset d'un ensemble en Java avec une complexité optimale

Le Powerset d'un ensemble est la collection de tous les sous-ensembles de cet ensemble. Pour un ensemble de n éléments, l'ensemble de puissances contient 2^n sous-ensembles.

Considérons un ensemble Java :

Set<Integer> mySet = new HashSet<>();
mySet.add(1);
mySet.add(2);
mySet.add(3);

Nous voulons écrire une fonction, getPowerset, pour générer l'ensemble de puissances de cet ensemble. La complexité idéale pour cette opération est O(2^n).

Une implémentation possible utilisant les génériques et les ensembles de Java est :

public static <T> Set<Set<T>> getPowerset(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 : getPowerset(rest)) {
        Set<T> newSet = new HashSet<>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }

    return sets;
}

Cette solution récursive parcourt les éléments de l'ensemble, les ajouter à chaque sous-ensemble et générer un nouveau sous-ensemble. Il maintient systématiquement l'ensemble des puissances des éléments restants.

Un test simple utilisant l'exemple d'entrée donne le résultat attendu :

for (Set<Integer> s : getPowerset(mySet)) {
    System.out.println(s);
}

Sortie :

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

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!