PowerSet Construction

well.. almost a year is passed from my last post.. :\ ugh. it must seems that i did nothing! while it’s quite true on the programming side.. it’s not so much true on life side. i just miss four exam, two apprenticeship and a thesis to get gratueted as IT engineer. So apart from my wasted social life, here it is one of my last work: an algoritm to compute a generic powerset construction. I did it while i was studying something about grammars and languages. So here it is, the program in java :)

Basically, a powerset construction it’s the set of all combinations of the items given, and the number of combinations is very simple to calculate: 2^x is the answer where x is the number of element to combine. well, after this we need to think how to pick the elements to write down all the combinations. we will have 2^x combinations starting from the empty set to the full elements set. but how to compute that on an easy way?
that is the basic idea: 2^x is our number of combinations (ugh i said it about twenty-eight times..) that can pratically be represented by a binary number where every digit represent an element.. then now we have now to include (or exclude) an element if its representative digit is one or zero.

So we will have just four elements a,b,c,d and we start from the binary number “0000” (if we have 4 element to combine) and we will exclude all the elements (empty set, represented with “{}”). Then we just need to “add 1” (logically, in binary!) to get the next set: “0001” -> {a}, sum 1, “0010” -> {b}, sum 1 again, “0011” -> {a,b}, sum 1, “0100” -> {c}, “0101” -> {a,c}, “0110” -> {b,c}, “0111” -> {a,b,c}, and go on till have “1111” -> {a,b,c,d}.. now let’s put all togheter to make our powerset construction!

{};{a,};{b,};{a,b,};{c,};{a,c,};{b,c,};{a,b,c,};{d,};{a,d,};{b,d,};{a,b,d,};{c,d,};{a,c,d,};{b,c,d,};{a,b,c,d,}

So that is the result.. but it’s very simple and a bit odd.. because it isn’t not in the standard order.. maybe one day i will improve the algoritm including ordering. not that hard to do.

well, here it is the code :) thank you for reading.

import java.util.Scanner;
import java.util.StringTokenizer;

public class Powerset {

	private int num;
	private boolean save_parts;
	private String string;
	private String elements[];
	private boolean binary[];
	private String parts[];
	
	public Powerset()
	{
		num=0;
		string="";		
		save_parts=false;
	}
	
	public void save_parts_on()
	{
		save_parts=true;
	}
	
	public void save_parts_off()
	{
		save_parts=false;
	}
	
	public void  insert_elements()
	{
		System.out.print("Please type in the elements separated by \"|\" symbol: ");
		Scanner scanner = new Scanner(System.in);
		string=scanner.next(); //carico la stringa digitata
		StringTokenizer token = new StringTokenizer(string, "|");
		int count = token.countTokens();
		elements = new String[count]; //dimensiono l'array degli elementi
		num=(int)Math.pow(2, count);
		if (save_parts) parts = new String[num];
		binary = new boolean[count]; //e quello dei valori binari
		
		count = 0;
		while (token.hasMoreTokens()) //prendo gli elementi uno ad uno e li assegno nel vettore
			elements[count++] = new String(token.nextToken());

		if (save_parts) 
			for (count=0; count<parts.length;count++) //azzero l'array parts
				parts[count]="";
		for (count=0; count<binary.length;count++) //azzero l'array binary
			binary[count]=false;
	}
	
	private void get_parts()
	{
		int num,i,j;
		if (!save_parts) System.out.print("PowerSet Construction: ");
		for (i=0; i<this.num; i++)
		{
			if (save_parts) parts[i]="{";
			else System.out.print("{");
			num=i;
			for (j=0; j<binary.length; j++)
			{
				if (num%2==1) binary[j]=true;
				else binary[j]=false;
				num=num/2;				
			}
			
			for (j=0; j<elements.length; j++)
			{
				if (binary[j]==true)	
				{
					if (save_parts) parts[i]+=elements[j]+",";
					else System.out.print(elements[j]+",");
				}
			}
			if (save_parts) parts[i]+="}";
			else System.out.print("};");
		}
	}
	
	public void print_parts()
	{
		int i;
		
		if (save_parts)
		{


			System.out.print("PowerSet Construction: ");
			//stampa le parti dell'insieme
			for (i=0; i<parts.length; i++)			System.out.print(parts[i]+";");
		}
		else			get_parts();
	}	
	
	public static void main(String[] args) 
	{
		Powerset  pippo = new Powerset();
		pippo.insert_elements();
		pippo.get_parts();
	}
}

One thought on “PowerSet Construction

  1. sundar

    please give codings to PowerSet Construction in c programming
    pls any body help me .

Leave a Reply

Your email address will not be published. Required fields are marked *