Skip to content

Commit 6a09f4a

Browse files
mnafshinmaibin
mnafshin
authored and
maibin
committed
PowerSet generation is Java and respective unit tests are added (BAEL-3417) (eugenp#8284)
* PowerSet generation is Java and respective unit tests are added * function name is adjusted to the actual ordering name (Reverse Lexicographical ordering) * Guava example test function is changed * LazyLoad powerSet (based on Guava implementation) is added * set is used instead of map.keySet()
1 parent a08f136 commit 6a09f4a

File tree

2 files changed

+545
-0
lines changed

2 files changed

+545
-0
lines changed

‎core-java-modules/core-java-lang-math/src/main/java/com/baeldung/powerset/PowerSetUtility.java‎

Lines changed: 320 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,320 @@
1+
package com.baeldung.powerset;
2+
3+
import com.google.common.collect.Sets;
4+
5+
import javax.annotation.Nullable;
6+
import java.util.AbstractSet;
7+
import java.util.ArrayList;
8+
import java.util.Arrays;
9+
import java.util.Collection;
10+
import java.util.HashMap;
11+
import java.util.HashSet;
12+
import java.util.Iterator;
13+
import java.util.List;
14+
import java.util.Map;
15+
import java.util.NoSuchElementException;
16+
import java.util.Set;
17+
18+
public class PowerSetUtility<T> {
19+
20+
private Map<T, Integer> map = new HashMap<>();
21+
private List<T> reverseMap = new ArrayList<>();
22+
23+
//Lazy Load PowerSet class
24+
private static class PowerSet<E> extends AbstractSet<Set<E>> {
25+
private Map<E, Integer> map = new HashMap<>();
26+
private List<E> reverseMap = new ArrayList<>();
27+
private Set<E> set;
28+
29+
public PowerSet(Set<E> set) {
30+
this.set = set;
31+
initializeMap();
32+
}
33+
34+
abstract class ListIterator<K> implements Iterator<K> {
35+
36+
protected int position = 0;
37+
private int size;
38+
39+
public ListIterator(int size) {
40+
this.size = size;
41+
}
42+
43+
@Override
44+
public boolean hasNext() {
45+
return position < size;
46+
}
47+
}
48+
49+
static class Subset<E> extends AbstractSet<E> {
50+
private Map<E, Integer> map;
51+
private List<E> reverseMap;
52+
private int mask;
53+
54+
public Subset(Map<E, Integer> map, List<E> reverseMap, int mask) {
55+
this.map = map;
56+
this.reverseMap = reverseMap;
57+
this.mask = mask;
58+
}
59+
60+
@Override
61+
public Iterator<E> iterator() {
62+
return new Iterator<E>() {
63+
int remainingSetBits = mask;
64+
65+
@Override
66+
public boolean hasNext() {
67+
return remainingSetBits != 0;
68+
}
69+
70+
@Override
71+
public E next() {
72+
int index = Integer.numberOfTrailingZeros(remainingSetBits);
73+
if (index == 32) {
74+
throw new NoSuchElementException();
75+
}
76+
remainingSetBits &= ~(1 << index);
77+
return reverseMap.get(index);
78+
}
79+
};
80+
}
81+
82+
@Override
83+
public int size() {
84+
return Integer.bitCount(mask);
85+
}
86+
87+
@Override
88+
public boolean contains(@Nullable Object o) {
89+
Integer index = map.get(o);
90+
return index != null && (mask & (1 << index)) != 0;
91+
}
92+
}
93+
94+
@Override
95+
public Iterator<Set<E>> iterator() {
96+
return new ListIterator<Set<E>>(this.size()) {
97+
@Override
98+
public Set<E> next() {
99+
return new Subset<>(map, reverseMap, position++);
100+
}
101+
};
102+
}
103+
104+
@Override
105+
public int size() {
106+
return (1 << this.set.size());
107+
}
108+
109+
@Override
110+
public boolean contains(@Nullable Object obj) {
111+
if (obj instanceof Set) {
112+
Set<?> set = (Set<?>) obj;
113+
return reverseMap.containsAll(set);
114+
}
115+
return false;
116+
}
117+
118+
@Override
119+
public boolean equals(@Nullable Object obj) {
120+
if (obj instanceof PowerSet) {
121+
PowerSet<?> that = (PowerSet<?>) obj;
122+
return set.equals(that.set);//Set equals check to have the same element regardless of the order of the items
123+
}
124+
return super.equals(obj);
125+
}
126+
127+
128+
private void initializeMap() {
129+
int mapId = 0;
130+
for (E c : this.set) {
131+
map.put(c, mapId++);
132+
reverseMap.add(c);
133+
}
134+
}
135+
}
136+
137+
public Set<Set<T>> lazyLoadPowerSet(Set<T> set) {
138+
return new PowerSet<>(set);
139+
}
140+
141+
public Set<Set<T>> recursivePowerSet(Set<T> set) {
142+
if (set.isEmpty()) {
143+
Set<Set<T>> ret = new HashSet<>();
144+
ret.add(set);
145+
return ret;
146+
}
147+
148+
T element = set.iterator().next();
149+
Set<T> subSetWithoutElement = getSubSetWithoutElement(set, element);
150+
Set<Set<T>> powerSetSubSetWithoutElement = recursivePowerSet(subSetWithoutElement);
151+
152+
Set<Set<T>> powerSetSubSetWithElement = addElementToAll(powerSetSubSetWithoutElement, element);
153+
154+
Set<Set<T>> powerSet = new HashSet<>();
155+
powerSet.addAll(powerSetSubSetWithoutElement);
156+
powerSet.addAll(powerSetSubSetWithElement);
157+
return powerSet;
158+
}
159+
160+
public Set<Set<T>> recursivePowerSetIndexRepresentation(Collection<T> set) {
161+
initializeMap(set);
162+
Set<Set<Integer>> powerSetIndices = recursivePowerSetIndexRepresentation(0, set.size());
163+
return unMapIndex(powerSetIndices);
164+
}
165+
166+
private List<List<Boolean>> iterativePowerSetByLoopOverNumbersWithReverseLexicographicalOrder(int n) {
167+
List<List<Boolean>> powerSet = new ArrayList<>();
168+
for (int i = 0; i < (1 << n); i++) {
169+
List<Boolean> subset = new ArrayList<>(n);
170+
for (int j = 0; j < n; j++)
171+
subset.add(((1 << j) & i) > 0);
172+
powerSet.add(subset);
173+
}
174+
return powerSet;
175+
}
176+
177+
private List<List<Boolean>> iterativePowerSetByLoopOverNumbersWithGrayCodeOrder(int n) {
178+
List<List<Boolean>> powerSet = new ArrayList<>();
179+
for (int i = 0; i < (1 << n); i++) {
180+
List<Boolean> subset = new ArrayList<>(n);
181+
for (int j = 0; j < n; j++) {
182+
int grayEquivalent = i ^ (i >> 1);
183+
subset.add(((1 << j) & grayEquivalent) > 0);
184+
}
185+
powerSet.add(subset);
186+
}
187+
return powerSet;
188+
}
189+
190+
public Set<Set<T>> recursivePowerSetBinaryRepresentation(Collection<T> set) {
191+
initializeMap(set);
192+
Set<List<Boolean>> powerSetBoolean = recursivePowerSetBinaryRepresentation(0, set.size());
193+
return unMapBinary(powerSetBoolean);
194+
}
195+
196+
public List<List<T>> iterativePowerSetByLoopOverNumbers(Set<T> set) {
197+
initializeMap(set);
198+
List<List<Boolean>> sets = iterativePowerSetByLoopOverNumbersWithReverseLexicographicalOrder(set.size());
199+
return unMapListBinary(sets);
200+
}
201+
202+
public List<List<T>> iterativePowerSetByLoopOverNumbersMinimalChange(Set<T> set) {
203+
initializeMap(set);
204+
List<List<Boolean>> sets = iterativePowerSetByLoopOverNumbersWithGrayCodeOrder(set.size());
205+
return unMapListBinary(sets);
206+
}
207+
208+
public static int getRankInLexicographicalOrder(List<Boolean> subset) {
209+
int rank = 0;
210+
for (int i = 0; i < subset.size(); i++)
211+
if (subset.get(i))
212+
rank += (1 << (subset.size() - i - 1));
213+
return rank;
214+
}
215+
216+
public static List<Boolean> getSubsetForRankInLexicographicalOrder(int rank, int sizeOfSet) {
217+
Boolean[] subset = new Boolean[sizeOfSet];
218+
for(int j = 0; j < sizeOfSet; j++) {
219+
subset[sizeOfSet - j - 1] = ((rank & (1 << j)) > 0);
220+
}
221+
return Arrays.asList(subset);
222+
}
223+
224+
private Set<Set<Integer>> recursivePowerSetIndexRepresentation(int idx, int n) {
225+
if (idx == n) {
226+
Set<Set<Integer>> empty = new HashSet<>();
227+
empty.add(new HashSet<>());
228+
return empty;
229+
}
230+
Set<Set<Integer>> powerSetSubset = recursivePowerSetIndexRepresentation(idx + 1, n);
231+
Set<Set<Integer>> powerSet = new HashSet<>(powerSetSubset);
232+
for (Set<Integer> s : powerSetSubset) {
233+
HashSet<Integer> subSetIdxInclusive = new HashSet<>(s);
234+
subSetIdxInclusive.add(idx);
235+
powerSet.add(subSetIdxInclusive);
236+
}
237+
return powerSet;
238+
}
239+
240+
private Set<List<Boolean>> recursivePowerSetBinaryRepresentation(int idx, int n) {
241+
if (idx == n) {
242+
Set<List<Boolean>> powerSetOfEmptySet = new HashSet<>();
243+
powerSetOfEmptySet.add(Arrays.asList(new Boolean[n]));
244+
return powerSetOfEmptySet;
245+
}
246+
Set<List<Boolean>> powerSetSubset = recursivePowerSetBinaryRepresentation(idx + 1, n);
247+
Set<List<Boolean>> powerSet = new HashSet<>();
248+
for (List<Boolean> s : powerSetSubset) {
249+
List<Boolean> subSetIdxExclusive = new ArrayList<>(s);
250+
subSetIdxExclusive.set(idx, false);
251+
powerSet.add(subSetIdxExclusive);
252+
List<Boolean> subSetIdxInclusive = new ArrayList<>(s);
253+
subSetIdxInclusive.set(idx, true);
254+
powerSet.add(subSetIdxInclusive);
255+
}
256+
return powerSet;
257+
}
258+
259+
private void initializeMap(Collection<T> collection) {
260+
int mapId = 0;
261+
for (T c : collection) {
262+
map.put(c, mapId++);
263+
reverseMap.add(c);
264+
}
265+
}
266+
267+
private Set<Set<T>> unMapIndex(Set<Set<Integer>> sets) {
268+
Set<Set<T>> ret = new HashSet<>();
269+
for (Set<Integer> s : sets) {
270+
HashSet<T> subset = new HashSet<>();
271+
for (Integer i : s)
272+
subset.add(reverseMap.get(i));
273+
ret.add(subset);
274+
}
275+
return ret;
276+
}
277+
278+
private Set<Set<T>> unMapBinary(Collection<List<Boolean>> sets) {
279+
Set<Set<T>> ret = new HashSet<>();
280+
for (List<Boolean> s : sets) {
281+
HashSet<T> subset = new HashSet<>();
282+
for (int i = 0; i < s.size(); i++)
283+
if (s.get(i))
284+
subset.add(reverseMap.get(i));
285+
ret.add(subset);
286+
}
287+
return ret;
288+
}
289+
290+
private List<List<T>> unMapListBinary(Collection<List<Boolean>> sets) {
291+
List<List<T>> ret = new ArrayList<>();
292+
for (List<Boolean> s : sets) {
293+
List<T> subset = new ArrayList<>();
294+
for (int i = 0; i < s.size(); i++)
295+
if (s.get(i))
296+
subset.add(reverseMap.get(i));
297+
ret.add(subset);
298+
}
299+
return ret;
300+
}
301+
302+
private Set<Set<T>> addElementToAll(Set<Set<T>> powerSetSubSetWithoutElement, T element) {
303+
Set<Set<T>> powerSetSubSetWithElement = new HashSet<>();
304+
for (Set<T> subsetWithoutElement : powerSetSubSetWithoutElement) {
305+
Set<T> subsetWithElement = new HashSet<>(subsetWithoutElement);
306+
subsetWithElement.add(element);
307+
powerSetSubSetWithElement.add(subsetWithElement);
308+
}
309+
return powerSetSubSetWithElement;
310+
}
311+
312+
private Set<T> getSubSetWithoutElement(Set<T> set, T element) {
313+
Set<T> subsetWithoutElement = new HashSet<>();
314+
for (T s : set) {
315+
if (!s.equals(element))
316+
subsetWithoutElement.add(s);
317+
}
318+
return subsetWithoutElement;
319+
}
320+
}

0 commit comments

Comments
 (0)