Share on Google+

# Java generate the powerset of a given set

Ads
In this section, you will learn how to generate the powerset of a given set of values using Java.

### Java generate the powerset of a given set

In this section, you will learn how to generate the powerset of a given set of values. As you have already know about the concept of set, which is the finite or infinite collection of objects and there is no order of significance and multiplicity. The Power Set is a set of all the subsets of these sets. For example,
if we have a set {x,y,z}:

1) The {x}, {y},{z}, {x,y}, {y,z}, {x,z} are its subset.
2) The {x,y,z} is also its subset.
3) The empty set {} is also its subset.

Now, the Power Set of {x,y,z} will be:  P(S) = { {}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z} }

Description of code:

In the given code, firstly we have specified the set and using Math.pow(2,len), we get the number of powerset elements where 'len' is the number of elements in the given set. After that, we have created a binary counter for the number of powerset elements and converted the binary numbers of the integer to a String .Then the following code convert each digit of the binary number to the corresponding element in the new set.

```for (int j = 0; j < pset.length(); j++) {
if (pset.charAt(j) == '1')
set.add(st[j]);
}
```

and at last we get the powerset of the given set.

Here is the code:

```import java.util.*;

public class PowerSet {
public static void main(String[] args) {
String st[] = { "x", "y", "z" };
LinkedHashSet hashSet = new LinkedHashSet();
int len = st.length;
int elements = (int) Math.pow(2, len);
for (int i = 0; i < elements; i++) {
String str = Integer.toBinaryString(i);
int value = str.length();
String pset = str;
for (int k = value; k < len; k++) {
pset = "0" + pset;
}
LinkedHashSet set = new LinkedHashSet();
for (int j = 0; j < pset.length(); j++) {
if (pset.charAt(j) == '1')
set.add(st[j]);
}
hashSet.add(set);
}
System.out.println(hashSet.toString().replace("[", "{").replace("]","}"));
}
}
```

Output:

 {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a,b, c}}

Advertisements

Ads

Posted on: March 13, 2010 If you enjoyed this post then why not add us on Google+? Add us to your Circles

Share this Tutorial Follow us on Twitter, or add us on Facebook or Google Plus to keep you updated with the recent trends of Java and other open source platforms.

Related Tutorials

Ads

Advertisement null

Ads