Set data structure problem
I'm trying to make a power set generator and I can't seem to figure out a way to recursively call the method right. Also I can't figure out how to only remove the first element then I can print the sets.
example Set S = [A, B , C]
then it prints
[ ] [A],, [C] ,[A, B], [B, C] [A, C] [A, B, C]
basically all the combinations. It's 2^n many combos... n = number of set elements.
Here is my code, does any one see the problem(s) ?
Thanks in advance.
mport java.util.*;
publicclass PowerSetGenerator{
publicstaticvoid main(String[] args)
{
Set<String> setA =new HashSet<String>();
setA.add("A");
setA.add("B");
setA.add("C");
System.out.println(generatePowerSet(setA));
}
publicstatic <E> Set<Set ><E>> generatePowerSet(Set<E> S)
{
if(S.isEmpty())
{
Set<E> emptySet =new HashSet<E>();
S.addAll(emptySet);
return (Set<Set><E>>) S;
}
else
{
Iterator<E> iter = S.iterator();
while(iter.hasNext()){
E nextItem = iter.next();
S.remove(nextItem);
break;
}
generatePowerSet(S);
return (Set<Set><E>>) S;
}
//return (Set<Set ><E>>) S;
}
}
> basically all the combinations. It's 2^n many
> combos... n = number of set elements.
True, and if you know how to count in binary, you can generate all
those sets. The following table might clarify this a bit:
A B Cresult
----
0 0 0 = []
0 0 1 = [ C ]
0 1 0 = [ B ]
0 1 1 = [ B C ]
1 0 0 = [ A ]
1 0 1 = [A C ]
1 1 0 = [ A B ]
1 1 1 = [ A B C ]
kind regards,
Jos
JosAHa at 2007-7-15 22:38:50 >
> okay but how do I use that table exactly? I mean yeah I was taught to
> do this assignment with that table...but how do I code it exactly?
Let 'n' be the width of that table, then '1<<n' is the length of that table.
The first entry equals 0 and the last entry equals '(1><<n)-1'. Counting
all the values is easy:for (int v= 0; v < (1<<n); v++)
...
for any value 'v' you want to know the bit values of 'v'. We know that
there are 'n' bits to consider so:for (int v= 0; v >< (1<<n); v++) {
for (int b= 0; b >< n; b++) {
if ((v&(1<<b)) != 0)
// bit b is set in value v
}
}
You should be able to take it from here.
kind regards,
Jos
ps. that '><' thingy you're reading is a forum formatting bug; it should read as '<'
JosAHa at 2007-7-15 22:38:50 >
