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