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

Générer le Powerset d'un ensemble en Java

Le Powerset d'un ensemble est l'ensemble de tous les sous-ensembles de cet ensemble. Par exemple, l'ensemble des puissances de {1, 2, 3} est :

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

Supposons que nous ayons un Set en Java :

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

Comment pouvons-nous écrire le fonction getPowerset avec la complexité temporelle optimale ?

Solution

La complexité temporelle de la fonction Powerset est O(2^n), où n est le nombre d'éléments dans l'ensemble. En effet, le powerset d'un ensemble avec n éléments contient 2^n sous-ensembles.

Voici une implémentation fonctionnelle de la fonction getPowerset utilisant des génériques et des ensembles :

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

Test

Testons la fonction getPowerset avec l'exemple donné input :

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

Cela imprimera le résultat suivant :

[]
[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!