Wednesday, July 9, 2008

Combination Generator program in java

This is a problem related to computability and complexity in computer science...Some problems in computer science cannot be resolved completely. Finding a correct solution might be impossible at some circumstances. Have you heard of these problems? Sorting, Partition problem, Halting problem. Here i present a case regarding partition problem.

The program takes numbers at run time and breaks it in to two sets where the sum of the elements in the two sets are equal. It should display the result, or it should say there are no such two sets in the given numbers. The time taken to get the solution against the numbers entered at run time is calculated. I started with 10 numbers and waited for the result. Then increased it to 14,16 and so on.. I hope you got a clear picture of what is happening now. Below is the program written in java. The timer runs in the program itself.

import java.math.BigInteger;
import java.io.*;
import java.awt.event.*;
import java.util.*;
import java.text.*;

public class CombinationGenerator {

private int[] a;
private int n;
private int r;
private BigInteger numLeft;
private BigInteger total;


// Constructor

public CombinationGenerator (int n, int r) {

if (r > n) {
throw new IllegalArgumentException ();
}
if (n < 1) {
throw new IllegalArgumentException ();
}
this.n = n;
this.r = r;
a = new int[r];
BigInteger nFact = getFactorial (n);
BigInteger rFact = getFactorial (r);
BigInteger nminusrFact = getFactorial (n - r);
total = nFact.divide (rFact.multiply (nminusrFact));
reset ();
}

// Reset

public void reset () {
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
numLeft = new BigInteger (total.toString ());
}

// Return number of combinations not yet generated

public BigInteger getNumLeft () {
return numLeft;
}

// Are there more combinations?

public boolean hasMore () {
return numLeft.compareTo (BigInteger.ZERO) == 1;
}

// Return total number of combinations

public BigInteger getTotal () {
return total;
}
// Compute factorial

private static BigInteger getFactorial (int n) {
BigInteger fact = BigInteger.ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply (new BigInteger (Integer.toString (i)));
}
return fact;
}

// Generate next combination (algorithm from Rosen p. 286)

public int[] getNext () {

if (numLeft.equals (total)) {
numLeft = numLeft.subtract (BigInteger.ONE);
return a;
}

int i = r - 1;
while (a[i] == n - r + i) {
i--;
}
a[i] = a[i] + 1;
for (int j = i + 1; j < r; j++) {
a[j] = a[i] + j - i;
}

numLeft = numLeft.subtract (BigInteger.ONE);
return a;

}

public static void main(String d[]) throws IOException{

long startTime; // Starting time of program, in milliseconds.
long endTime; // Time when computations are done, in milliseconds.
double time; // Time difference, in seconds.


//get the number of numbers in set
InputStreamReader reader = new InputStreamReader (System.in);
BufferedReader input = new BufferedReader(reader);
System.out.print("Enter the numer of numbers in you set=");
String p = input.readLine();
int q =Integer.parseInt(p);
//put the elements to an array

int sum_of_array=0;
int[] indices;
int elements[]=new int[q];
int half_of_set=0;
int sum_of_elm=0;

for(int r=0; r<q; r++){

System.out.print("Enter the numbers of your set=");
String c = input.readLine();
int e =Integer.parseInt(c);
elements[r]= e;
}
//get the sum of array
for(int x=0; x<elements.length; x++){
sum_of_array=sum_of_array+elements[x];
}
int reminder=sum_of_array % 2;
half_of_set=sum_of_array/2;

//
if(reminder==0){
startTime = System.currentTimeMillis();
for(int len_of_array=1;len_of_array<=elements.length;len_of_array++ ){

CombinationGenerator x = new CombinationGenerator (elements.length, len_of_array);
StringBuffer combination;
while (x.hasMore ()) {

combination = new StringBuffer ();
indices = x.getNext ();
for (int i = 0; i < indices.length; i++) {

sum_of_elm=sum_of_elm+elements[indices[i]];

}

if(half_of_set==sum_of_elm){


//print the sub set element

for(int g=0; g<indices.length; g++){
System.out.println("numbers in your one sub set are ="+elements[indices[g]]+",");

}
endTime = System.currentTimeMillis();
time = (endTime - startTime) / 1000.0;
System.out.println(time);

return;
}

sum_of_elm=0;//set the sum of elm to 0
}
}
endTime = System.currentTimeMillis();
time = (endTime - startTime) / 1000.0;
System.out.println(time);

}else{
System.out.println("given number set can not divide to two equal sets:Sorry");

}
}

}

The maximum number of numbers i could enter was 36..i couldn't go beyond that..the program stopped running....it explains the complexity of the problem. Finally the output was shown in a graph as below..