Obtaining a Powerset of a Set in Java

Obtaining a powerset of a set in Java

Yes, it is O(2^n) indeed, since you need to generate, well, 2^n possible combinations. Here's a working implementation, using generics and sets:

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<Set<T>>();
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<T>());
        return sets;
    }
    List<T> list = new ArrayList<T>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
    for (Set<T> set : powerSet(rest)) {
        Set<T> newSet = new HashSet<T>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }       
    return sets;
}  

And a test, given your example input:

 Set<Integer> mySet = new HashSet<Integer>();
 mySet.add(1);
 mySet.add(2);
 mySet.add(3);
 for (Set<Integer> s : SetUtils.powerSet(mySet)) {
     System.out.println(s);
 }

How to generate the power-set of a given List?

What you're looking for is essentially the power set (minus perhaps the empty set). Guava actually has a method for this: Sets.powerSet(). You can view the source of the Sets class to see how the method is implemented if you want to write it yourself; you might need to modify it to return a List instead of a Set since you want to preserve order, although this change should not be too drastic. Once you have the power set, it should be trivial to iterate over it and construct the map you want.

Generating all the elements of a power set

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;
}

Best way to get a power set of an array?

Try this.

int[] a = {1, 2};
int max = 1 << a.length;
int[][] result = new int[max][];
for (int i = 0; i < max; ++i) {
    result[i] = new int[Integer.bitCount(i)];
    for (int j = 0, b = i, k = 0; j < a.length; ++j, b >>= 1)
        if ((b & 1) != 0)
            result[i][k++] = a[j];
}
System.out.println(Arrays.deepToString(result));

result:

[[], [1], [2], [1, 2]]

Finding Power set of a Set

To output the Power Set,there are three ways in "14.5 Generating Subsets", The Alogrithm Design Manual,and I have tried all of them with only array,loop and functions. But there will be no code.Here are short paragraphs about them:

1.Lexicographic order – Lexicographic order means sorted order, and is
often the most natural way to generate combinatorial objects. The
eight subsets of {1, 2, 3} in lexicographic order are {} , {1}, {1,
2}, {1, 2, 3}, {1, 3}, {2}, {2, 3}, and {3}. But it is surprisingly
difficult to generate subsets in lexicographic order. Unless you have
a compelling reason to do so, don’t bother.

2.Gray Code – A particularly interesting and useful subset sequence is the minimum change order, wherein adjacent subsets differ by the
insertion or deletion of exactly one element. Such an ordering, called
a Gray code. Generating subsets in Gray code order can be very fast,
because there is a nice recursive construction. Construct a Gray code
of n − 1 elements G_n−1 Reverse a > second copy of G_n−1 and add n to
each subset in this copy. Then concatenate them together to create G_n .
Further, since only one element changes between subsets, exhaustive
search algorithms built on Gray codes can be quite efficient.

3.Binary counting– The simplest approach to subset-generation problems is based on the observation that any subset S' is defined by
the items of that S are in S'. We can represent S' by a binary string
ofn bits, where bit i is 1iffthe ith element of S is in S'. This
defines a bijection between the 2ⁿ binary strings of length
n,and the 2ⁿ subsets of n items. For n = 3, binary counting
generates subsets in the following order: {} , {3}, {2}, {2,3}, {1},
{1,3}, {1,2}, {1,2,3}. This binary representation is the key to
solving all subset generation problems. To generate all subsets in
order, simply count from 0 to 2^n-1. For each integer,
successively mask off each of the bits and compose a subset of exactly
the items corresponding to 1 bits. To generate the next or previous
subset, increment or decrement the integer by one.Unranking a subset
is ex-actly the masking procedure, while ranking constructs a binary
number with 1’s corresponding to items in S and then converts this
binary number to an integer.

if you want an easy one, just Binary Counting is enough, it can be recurrence implement such as backtracking or a specific one.If you have done it and want more challenge,you can code a Gray Code one. You can learn how to generate Gray Code on its wiki page here.

---

Related Topics