Home Tutorial Java Core Java generate the powerset of a given set

 
 

Share on Google+Share on Google+
Java generate the powerset of a given set
Posted on: March 13, 2010 at 12:00 AM
Advertisement
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}}
Advertisement

Related Tags for Java generate the powerset of a given set:


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.

Posted on: March 13, 2010

Recommend the tutorial

Advertisements Advertisements
 

 

 

DMCA.com