Everything is in the title .. =)
I want to create a powerset fastly, only with subset of length between 3 (minimum constant length) and a maximum. This maximum should be 5 most of the times but I want it variable (from 3 to 5,6). The original set may be large. I need to store theses subset for further processing.
I've seen Obtaining a powerset of a set in Java, but here they generate every subset of the power set. I've also seen efficient powerset algorithm for subsets of minimal length , for C#, but I think ,as Adam S said, I will run into low running time performances and memory issues.
I'd like to combine theses ideas into an ideal one for my goal. My last hope would be to generate every subset fastly ( maybe with the algorithm in Guava ) and to iterate over to take only with desired length...but even to read it's ugly ;)
Anyone got ideas ?
I borrowed heavily from st0le's answer.
Basically, as I iterated through the bit array that was controlling the set generation, I checked to make sure that the number of bits was between the minimum and maximum.
Here's the code.
import java.util.BitSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class PowerSet<E> implements Iterator<Set<E>>, Iterable<Set<E>> {
private int minSize;
private int maxSize;
private E[] arr = null;
private BitSet bset = null;
@SuppressWarnings("unchecked")
public PowerSet(Set<E> set, int minSize, int maxSize) {
this.minSize = Math.min(minSize, set.size());
this.maxSize = Math.min(maxSize, set.size());
arr = (E[]) set.toArray();
bset = new BitSet(arr.length + 1);
for (int i = 0; i < minSize; i++) {
bset.set(i);
}
}
@Override
public boolean hasNext() {
return !bset.get(arr.length);
}
@Override
public Set<E> next() {
Set<E> returnSet = new TreeSet<E>();
// System.out.println(printBitSet());
for (int i = 0; i < arr.length; i++) {
if (bset.get(i)) {
returnSet.add(arr[i]);
}
}
int count;
do {
incrementBitSet();
count = countBitSet();
} while ((count < minSize) || (count > maxSize));
// System.out.println(returnSet);
return returnSet;
}
protected void incrementBitSet() {
for (int i = 0; i < bset.size(); i++) {
if (!bset.get(i)) {
bset.set(i);
break;
} else
bset.clear(i);
}
}
protected int countBitSet() {
int count = 0;
for (int i = 0; i < bset.size(); i++) {
if (bset.get(i)) {
count++;
}
}
return count;
}
protected String printBitSet() {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < bset.size(); i++) {
if (bset.get(i)) {
builder.append('1');
} else {
builder.append('0');
}
}
return builder.toString();
}
@Override
public void remove() {
throw new UnsupportedOperationException("Not Supported!");
}
@Override
public Iterator<Set<E>> iterator() {
return this;
}
public static void main(String[] args) {
Set<Character> set = new TreeSet<Character>();
for (int i = 0; i < 7; i++)
set.add((char) (i + 'A'));
PowerSet<Character> pset = new PowerSet<Character>(set, 3, 5);
int count = 1;
for (Set<Character> s : pset) {
System.out.println(count++ + ": " + s);
}
}
}
And here are the test results:
1: [A, B, C]
2: [A, B, D]
3: [A, C, D]
4: [B, C, D]
5: [A, B, C, D]
6: [A, B, E]
7: [A, C, E]
8: [B, C, E]
9: [A, B, C, E]
10: [A, D, E]
11: [B, D, E]
12: [A, B, D, E]
13: [C, D, E]
14: [A, C, D, E]
15: [B, C, D, E]
16: [A, B, C, D, E]
17: [A, B, F]
18: [A, C, F]
19: [B, C, F]
20: [A, B, C, F]
21: [A, D, F]
22: [B, D, F]
23: [A, B, D, F]
24: [C, D, F]
25: [A, C, D, F]
26: [B, C, D, F]
27: [A, B, C, D, F]
28: [A, E, F]
29: [B, E, F]
30: [A, B, E, F]
31: [C, E, F]
32: [A, C, E, F]
33: [B, C, E, F]
34: [A, B, C, E, F]
35: [D, E, F]
36: [A, D, E, F]
37: [B, D, E, F]
38: [A, B, D, E, F]
39: [C, D, E, F]
40: [A, C, D, E, F]
41: [B, C, D, E, F]
42: [A, B, G]
43: [A, C, G]
44: [B, C, G]
45: [A, B, C, G]
46: [A, D, G]
47: [B, D, G]
48: [A, B, D, G]
49: [C, D, G]
50: [A, C, D, G]
51: [B, C, D, G]
52: [A, B, C, D, G]
53: [A, E, G]
54: [B, E, G]
55: [A, B, E, G]
56: [C, E, G]
57: [A, C, E, G]
58: [B, C, E, G]
59: [A, B, C, E, G]
60: [D, E, G]
61: [A, D, E, G]
62: [B, D, E, G]
63: [A, B, D, E, G]
64: [C, D, E, G]
65: [A, C, D, E, G]
66: [B, C, D, E, G]
67: [A, F, G]
68: [B, F, G]
69: [A, B, F, G]
70: [C, F, G]
71: [A, C, F, G]
72: [B, C, F, G]
73: [A, B, C, F, G]
74: [D, F, G]
75: [A, D, F, G]
76: [B, D, F, G]
77: [A, B, D, F, G]
78: [C, D, F, G]
79: [A, C, D, F, G]
80: [B, C, D, F, G]
81: [E, F, G]
82: [A, E, F, G]
83: [B, E, F, G]
84: [A, B, E, F, G]
85: [C, E, F, G]
86: [A, C, E, F, G]
87: [B, C, E, F, G]
88: [D, E, F, G]
89: [A, D, E, F, G]
90: [B, D, E, F, G]
91: [C, D, E, F, G]