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

WWTBAFM OQM – Offline Questions Manager :)

YvanSoftware is coding an offline questions writer for WWTBAFM! that’s very cool for who want to develop questions without access to internet. if you want to add the questions written with this software, you must email me the questions file, specifying the language, and i’ll add it to the database :)

here it is the website of this nice project!

WWTBAFM v0.7

WWTBAFM v0.7 is out with a gfx! this is a temporary release, because sephzero will redesign the entire gfx and some animations will be added.

[change log]

  • it uses a gfx! wow!
  • play with the Stylus (keys are no more supported, exeption is Start)
  • the game now will check if you questions’ file has more than 15 question without freeze
  • added a menu

Please add more questions! French and Spanish player still doesn’t have more than 5 questions for each difficulty!


WWTBAFM V0.7 (1) WWTBAFM V0.7 (2) WWTBAFM V0.7 (3)
WWTBAFM V0.7 (4) WWTBAFM V0.7 (5) WWTBAFM V0.7 (6)

Sourced Removed :\

hi! i don’t know if you know what happen to DragonMinded DSOrganize but this forced me to remove all the source of my works (apart from PAFont that wasn’t a program of mine. i just upgraded the code :) ). This doesn’t means that my works aren’t opensource because you can feel free to ask me about source codes. I’ll be happy to share my knowledge with you.

WWTBAFM is under development and the “basic&ugly” gfx is almost done. please come back later :)

who wants to do a new gfx?

i don’t want to wait anymore. everyone that want to help this project can try to do a gfx and starts hope that it will be the official skin of WWTBAFM. This will be a sort of contest. You can send your work at lottiATfastwebnetDOTit. Then i’ll post all the entries and people will choose (by vote) the best skin. :)

SOME SPECS:
read the first 3-4 paragraphs of palib’s sprites tutorials