Generate all elements of a power set

Question

/*
 * 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 2N 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;
import java.util.List;
import java.util.ArrayList;
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 });
 // get the index of truth values.
 for (int e = bitSet.nextSetBit(0); e != -1; e = bitSet.nextSetBit(e + 1)) {
 subset.add(ary[e]);
 }
 i++;
 return subset;
 }
 // Unit Test
 public static void main(String[] args) {
 Set<Integer> numbers = new TreeSet<Integer>();
 for (int i = 1; i < 5; i++) {
 numbers.add(i);
 }
 int count = 0;
 PowerSet<Integer> pSet = new PowerSet<Integer>(numbers);
 for (Set<Integer> subset : pSet) {
 //System.out.println(subset);
 count++;
 }
 assert count == (int)Math.pow(2, numbers.size()): "Total number of elements should be 2^N";
 }
}

The code is running fine. I am trying to learn assert for unit testing the code as well. The main issue is the elements seem to come out of order. Is there any way to maintain lexicographical order?

Answer 1

Power of 2

Instead of using:

(int)Math.pow(2, numbers.size())

You can compute a power of two more efficiently like this:

1 << numbers.size()

You can use 1L to compute it as a long if you think that the power may exceed 31.

Manual bit manipulation

Instead of using a BitSet to find the 1 bits in your int, you can use integer arithmetic to check the bits yourself:

 for (int bit = 0; bit < 32; bit++) {
 if ((i & (1 << bit)) != 0) {
 subset.add(ary[bit]);
 }
 }

Answer 2

regarding maintaining order - i think if you define subset as SortedSet (which is another interface that TreeSet implements) then you will get a subset where the elements are ordered according to their natural ordering (which is lexicographical), providing they are Strings of course.

regarding unit testing, the de-facto standard framework in Java is Junit, which uses assert and enhances it.

• CodeYogi: I have used assert in main method. Isn't this sufficient for programming practices?
• Sharon Ben Asher: you have only one test case? really? there are usually more. consider edge cases of null arg, empty set arg, etc. junit is a good framework for developing and maintaining a suite of test cases
• CodeYogi: Ah, ya I agree that was just start, I will surely add more tests in fact I need to learn testing properly too. Sure I will have a look into JUnit too.

Answer 3

* It's well-known that there are 2N elements in this set

You mean 2^N.

import java.util.List;
import java.util.ArrayList;

These imports are unused.

private final E[] ary;

Spell out the full name: array. Or better, use a name which describes the purpose of this field, like allElements.

private final int subsets;

This should be numSubsets.

private int i;

i is too short a name for a field. Consider using currentSubsetIndex or another descriptive name.

ary = (E[])set.toArray();

This triggers an unchecked operation warning. You may want to use @SuppressWarnings("unchecked") before the constructor or use this version of Set#toArray. I don't know what is the preferred way.

numSubsets = (int)Math.pow(2, array.length) - 1;

Use bit shifting as @JS1 suggests to avoid floating point rounding issues.

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

Calling iterator on the same PowerSet returns the same object. Therefore looping twice over the same PowerSet using a for-each loop won't work as expected. Iterables are not Iterators.

---

I also recommend that you use @JS1's implementation of next, and learn how to use JUnit as @sharonbn suggested. (Maybe the test suite would make good reviewable code too.)

---

EDIT:

The main issue is the elements seem to come out of order. Is there any way to maintain lexicographical order?

Sets are unordered. If you want a specific order for the subsets' elements, don't use Set (for input or output).