Maison >Java >javaDidacticiel >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!