CODEWITHSUNDEEP
algorithmdata-structuresjava-7
CodeYogi
CodeYogi

Reputation: 1412

Generating all the elements of a power set

Power set is just set of all subsets for given set. It includes all subsets (with empty set). It's well-known that there are 2^N elements in this set, where N is count of elements in original set.

To build power set, following thing can be used:

Create a loop, which iterates all integers from 0 till 2^N-1 Proceed to binary representation for each integer Each binary representation is a set of N bits (for lesser numbers, add leading zeros). Each bit corresponds, if the certain set member is included in current subset. 

import java.util.NoSuchElementException;
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 final E[] ary;
    private final int subsets;
    private int i;

    public PowerSet(Set<E> set) {
        ary = (E[])set.toArray();
        subsets = (int)Math.pow(2, ary.length) - 1;
    }

    public Iterator<Set<E>> iterator() {
        return this;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Cannot remove()!");
    }

    @Override
    public boolean hasNext() {
        return i++ < subsets;
    }

    @Override
    public Set<E> next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        Set<E> subset = new TreeSet<E>();
        BitSet bitSet = BitSet.valueOf(new long[] { i });
        if (bitSet.cardinality() == 0) {
            return subset;
        }
        for (int e = bitSet.nextSetBit(0); e != -1; e = bitSet.nextSetBit(e + 1)) {
            subset.add(ary[e]);
        }

        return subset;
    }

    // Unit Test
    public static void main(String[] args) {
        Set<Integer> numbers = new TreeSet<Integer>();
        for (int i = 1; i < 4; i++) {
            numbers.add(i);
        }
        PowerSet<Integer> pSet = new PowerSet<Integer>(numbers);
        for (Set<Integer> subset : pSet) {
            System.out.println(subset);
        }
    }
}

The output I am getting is:

[2]
[3]
[2, 3]
java.util.NoSuchElementException
    at PowerSet.next(PowerSet.java:47)
    at PowerSet.next(PowerSet.java:20)
    at PowerSet.main(PowerSet.java:67)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:606)
    at edu.rice.cs.drjava.model.compiler.JavacCompiler.runCommand(JavacCompiler.java:272)

So, the problems are:

  1. I am got getting all the elements(debugging shows me next is called only for even i's).
  2. The exception should not have been thrown.

Upvotes: 1

Views: 353

Answers (1)

sve
sve

Reputation: 4356

The problem is in your hasNext. You have i++ < subsets there. What happens is that since hasNext is called once from next() and once more during the iteration for (Set<Integer> subset : pSet) you increment i by 2 each time. You can see this since

for (Set<Integer> subset : pSet) {

}

is actually equivalent to:

Iterator<PowerSet> it = pSet.iterator();
while (it.hasNext()) {
    Set<Integer> subset = it.next();
}

Also note that 

if (bitSet.cardinality() == 0) {
    return subset;
}

is redundant. Try instead:

@Override
public boolean hasNext() {
    return i <= subsets;
}

@Override
public Set<E> next() {
    if (!hasNext()) {
        throw new NoSuchElementException();
    }
    Set<E> subset = new TreeSet<E>();
    BitSet bitSet = BitSet.valueOf(new long[] { i });
    for (int e = bitSet.nextSetBit(0); e != -1; e = bitSet.nextSetBit(e + 1)) {
        subset.add(ary[e]);
    }
    i++;

    return subset;
}

Upvotes: 1

Related Questions