Skip to content

Commit 3b3880a

Browse files
mnafshinmaibin
mnafshin
authored and
maibin
committed
Powerset (eugenp#8475)
* 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() * Lexicographic Order and Gray Order are removed from function names. Unused function (rank and unrank), which are not used in the text, are removed
1 parent 0d94a27 commit 3b3880a

2 files changed

Lines changed: 5 additions & 59 deletions

File tree

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

Lines changed: 4 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,5 @@
11
package com.baeldung.powerset;
22

3-
import com.google.common.collect.Sets;
4-
53
import javax.annotation.Nullable;
64
import java.util.AbstractSet;
75
import java.util.ArrayList;
@@ -163,7 +161,7 @@ public Set<Set<T>> recursivePowerSetIndexRepresentation(Collection<T> set) {
163161
return unMapIndex(powerSetIndices);
164162
}
165163

166-
private List<List<Boolean>> iterativePowerSetByLoopOverNumbersWithReverseLexicographicalOrder(int n) {
164+
private List<List<Boolean>> iterativePowerSetByLoopOverNumbers(int n) {
167165
List<List<Boolean>> powerSet = new ArrayList<>();
168166
for (int i = 0; i < (1 << n); i++) {
169167
List<Boolean> subset = new ArrayList<>(n);
@@ -174,7 +172,7 @@ private List<List<Boolean>> iterativePowerSetByLoopOverNumbersWithReverseLexicog
174172
return powerSet;
175173
}
176174

177-
private List<List<Boolean>> iterativePowerSetByLoopOverNumbersWithGrayCodeOrder(int n) {
175+
private List<List<Boolean>> iterativePowerSetByLoopOverNumbersWithMinimalChange(int n) {
178176
List<List<Boolean>> powerSet = new ArrayList<>();
179177
for (int i = 0; i < (1 << n); i++) {
180178
List<Boolean> subset = new ArrayList<>(n);
@@ -195,32 +193,16 @@ public Set<Set<T>> recursivePowerSetBinaryRepresentation(Collection<T> set) {
195193

196194
public List<List<T>> iterativePowerSetByLoopOverNumbers(Set<T> set) {
197195
initializeMap(set);
198-
List<List<Boolean>> sets = iterativePowerSetByLoopOverNumbersWithReverseLexicographicalOrder(set.size());
196+
List<List<Boolean>> sets = iterativePowerSetByLoopOverNumbers(set.size());
199197
return unMapListBinary(sets);
200198
}
201199

202200
public List<List<T>> iterativePowerSetByLoopOverNumbersMinimalChange(Set<T> set) {
203201
initializeMap(set);
204-
List<List<Boolean>> sets = iterativePowerSetByLoopOverNumbersWithGrayCodeOrder(set.size());
202+
List<List<Boolean>> sets = iterativePowerSetByLoopOverNumbersWithMinimalChange(set.size());
205203
return unMapListBinary(sets);
206204
}
207205

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-
224206
private Set<Set<Integer>> recursivePowerSetIndexRepresentation(int idx, int n) {
225207
if (idx == n) {
226208
Set<Set<Integer>> empty = new HashSet<>();

‎core-java-modules/core-java-lang-math/src/test/java/com/baeldung/powerset/PowerSetUtilityUnitTest.java‎

Lines changed: 1 addition & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -137,7 +137,7 @@ public void givenSet_WhenPowerSetIsCalculatedIterativePowerSetByLoopOverNumbers_
137137
}
138138

139139
@Test
140-
public void givenSet_WhenPowerSetIsCalculatedIterativePowerSetByLoopOverNumbersMinimalChange_ThenItContainsAllSubsetsInGrayOrder() {
140+
public void givenSet_WhenPowerSetIsCalculatedIterativePowerSetByLoopOverNumbersWithMinimalChange_ThenItContainsAllSubsets() {
141141

142142
Set<String> set = RandomSetOfStringGenerator.generateRandomSet();
143143
List<List<String>> powerSet = new PowerSetUtility<String>().iterativePowerSetByLoopOverNumbersMinimalChange(set);
@@ -172,42 +172,6 @@ public void givenSet_WhenPowerSetIsCalculatedIterativePowerSetByLoopOverNumbersM
172172
}
173173
}
174174

175-
@Test
176-
public void givenSubset_WhenPowerSetIsInLexicographicalOrder_ReturnCorrectRank() {
177-
int n = new Random().nextInt(5) + 5; //a number in [5, 10)
178-
for(int i = 0; i < ( 1 << n); i++) {
179-
Boolean[] subset = new Boolean[n];
180-
for(int j=0; j < n; j++) {
181-
subset[n - j - 1] = ((i & (1 << j)) > 0);
182-
}
183-
Assertions.assertEquals(i, PowerSetUtility.getRankInLexicographicalOrder(Arrays.asList(subset)));
184-
}
185-
}
186-
187-
@Test
188-
public void givenRanking_WhenPowerSetIsInLexicographicalOrder_ReturnTheSubset() {
189-
int n = new Random().nextInt(5) + 5; //a number in [5, 10)
190-
List<List<Boolean>> powerSet = new ArrayList<>();
191-
for(int i = 0; i < (1 << n); i++) {
192-
powerSet.add(PowerSetUtility.getSubsetForRankInLexicographicalOrder(i, n));
193-
}
194-
//To make sure that the size of power set is (2 power n)
195-
MatcherAssert.assertThat(powerSet, IsCollectionWithSize.hasSize((1 << n)));
196-
//To make sure that number of occurrence of each index is (2 power n-1)
197-
Map<Integer, Integer> counter = new HashMap<>();
198-
for (List<Boolean> subset : powerSet) {
199-
for (int i = 0; i < subset.size(); i++) {
200-
if(subset.get(i)) {
201-
int num = counter.getOrDefault(i, 0);
202-
counter.put(i, num + 1);
203-
}
204-
}
205-
}
206-
counter.forEach((k, v) -> Assertions.assertEquals((1 << (n - 1)), v.intValue()));
207-
//To make sure that one subset is not generated twice
208-
Assertions.assertEquals(powerSet.size(), new HashSet<>(powerSet).size());
209-
}
210-
211175
static class RandomSetOfStringGenerator {
212176
private static List<String> fruits = Arrays.asList("Apples", "Avocados", "Banana", "Blueberry", "Cherry", "Clementine", "Cucumber", "Date", "Fig",
213177
"Grapefruit"/*, "Grape", "Kiwi", "Lemon", "Mango", "Mulberry", "Melon", "Nectarine", "Olive", "Orange"*/);

0 commit comments

Comments
 (0)