package JavaApplication42;
import java.io.*;
import java.io.IOException;
import java.util.*;
import java.io.BufferedReader;
public class DPmodification {
public static void main(String[] args) {
BufferedReader br = null;
int n, c, d,k, swap,i=0,j=0,no_of_selected_item=0;
int numItems;
int numTransactions;
double minSup;
String configFile = "F:\\New Folder\\configtrial.txt";
try{
FileInputStream file_in = new FileInputStream(configFile);
BufferedReader data_in = new BufferedReader(new InputStreamReader(file_in));
//number of items
numItems = Integer.valueOf(data_in.readLine()).intValue();
boolean[] skiplist=new boolean[numItems];
//number of transactions
numTransactions = Integer.valueOf(data_in.readLine()).intValue();
//minsup
minSup = (Double.valueOf(data_in.readLine()).doubleValue());
int[] length=new int[numTransactions];
int[] sum=new int[numItems];
int[][] m=new int[numTransactions][numItems];
String[] line=new String[numTransactions];
//output config info to the user
System.out.print("\nInput configuration: " + numItems + " items, " + numTransactions + " transactions, ");
System.out.println("minsup = " + minSup + "%");
System.out.println();
minSup=(numTransactions*minSup)/100;
System.out.println("Min sup :"+minSup);
Date tim;
long start, end;
tim = new Date();
start = tim.getTime();
String sCurrentLine;
br = new BufferedReader(new FileReader("F:\\New Folder\\trantrial.txt"));
while ((sCurrentLine = br.readLine()) != null)
{
System.out.println(sCurrentLine);
line[i]=sCurrentLine;
i++;
}
int col=0;
for(i=0;i<numTransactions;i++)
{
for(j=0;j<numItems;j++)
{
String s=""+line[i].charAt(j);
m[i][j]=Integer.parseInt(s);
// System.out.println(m[i][j]);
}
}
//sum of columns
for(j=0;j<numItems;j++)
{
sum[j]=0;
for(i=0;i<numTransactions;i++)
{
String s=""+m[i][j];
//System.out.print(s);
sum[j]=sum[j]+Integer.parseInt(s);
}
if(sum[j]<minSup)
skiplist[j]=false;
else
{
skiplist[j]=true;
no_of_selected_item++;
}
}
for(i=0;i<numItems;i++)
{
System.out.print(" "+sum[i]);
}
int matrix2[][]=new int[numTransactions+1][no_of_selected_item+1];
System.out.println();
System.out.println("First Frequent Item Set");
j=0;
for(i=0;i<numItems;i++)
{
if(skiplist[i]==true)
{
matrix2[0][j]=i+1;
j++;
//System.out.print(" "+sum[i]);
}
}
System.out.println();
System.out.println("Total no of frequent 1 itemset :"+no_of_selected_item);
k=0;
for(j=0;j<numItems;j++)
{
if(skiplist[j]==true)
{
for(i=1;i<numTransactions+1;i++)
{
matrix2[i][k]=m[i-1][j];
}
k++;
}
}
System.out.println("Frequent 1 itemset");
for(i=0;i<no_of_selected_item;i++)
{System.out.print(" ");
System.out.print(matrix2[0][i]);
}
System.out.println("New Value of array");
for(i=0;i<no_of_selected_item;i++)
System.out.print(matrix2[0][i]);
System.out.println();
System.out.println("----------------------------------");
for(i=1;i<numTransactions+1;i++)
{
length[i-1]=0;
for(j=0;j<no_of_selected_item;j++)
{
System.out.print(" "+matrix2[i][j]);
//length of rows(no of 1's)
if(matrix2[i][j]==1)
length[i-1]++;
}
matrix2[i][no_of_selected_item]=length[i-1];
System.out.println(" "+length[i-1]);
}
System.out.println("Now sorting");
//Sorting
n=numTransactions;
for ( c = 0; c < ( n - 1 ); c++)
{
for ( d = 0; d < n - c - 1; d++)
{
if (matrix2[d+1][no_of_selected_item] < matrix2[d+2][no_of_selected_item]) // For descending order use <
{
swap = matrix2[d+1][no_of_selected_item];
matrix2[d+1][no_of_selected_item] = matrix2[d+2][no_of_selected_item];
matrix2[d+2][no_of_selected_item] = swap;
for(i=0;i<no_of_selected_item;i++)
{
swap = matrix2[d+1][i];
matrix2[d+1][i] = matrix2[d+2][i];
matrix2[d+2][i] = swap;
}
}
}
}
//Sorted Array
for(i=0;i<numTransactions;i++)
{
for(j=0;j<no_of_selected_item;j++)
{//System.out.print("till now");
System.out.print(matrix2[i][j]);
}
System.out.println(" "+matrix2[i][no_of_selected_item]);
}
int unique[][]=new int[numTransactions+1][no_of_selected_item+2];
System.out.println("printing");
//Sorted array display and creating new array
for(i=0;i<numTransactions+1;i++)
{
for(j=0;j<=no_of_selected_item;j++)
{
System.out.print(matrix2[i][j]);
unique[i][j]=matrix2[i][j];
}
unique[i][no_of_selected_item+1]=1;
System.out.println(" "+matrix2[i][no_of_selected_item]);
}
int no_trans=numTransactions+1;
//Removing redundancy
System.out.print("from here");
for(i=1;i<no_trans;i++)
{
if(unique[i][no_of_selected_item+1]!=0)
{
for(j=i+1;j<no_trans;j++)
{
if(matrix2[i][no_of_selected_item]==matrix2[j][no_of_selected_item] && unique[j][no_of_selected_item+1]!=0)
{
for(k=0;k<no_of_selected_item;k++)
{
if(matrix2[i][k]==matrix2[j][k])
{
if(k==no_of_selected_item-1)
{
unique[i][no_of_selected_item+1]++;
unique[j][no_of_selected_item+1]=0;
}
}
else
break;
}
}
}
}
}
System.out.println("ok");
for(i=0;i<no_trans;i++)
{
if(unique[i][no_of_selected_item+1]!=0)
{
if(unique[i][no_of_selected_item]>1)
{
for(j=0;j<no_of_selected_item;j++)
{
System.out.print(unique[i][j]);
}
System.out.println(" "+unique[i][j]+" "+unique[i][j+1]);
if(unique[i][j+1]>minSup)
{
//CALL FUNCTION FOR CALLING SUBSETS
}
}
}
}
/* int maxlength;
maxlength=unique[1][no_of_selected_item];
boolean[] skiplist2=new boolean[no_of_selected_item];
for(i=0;i<no_trans;i++)
{
if(unique[i][no_of_selected_item]!=maxlength)
{ for(j=0;j<no_of_selected_item;j++)
{if(unique[i][j]==1)
skiplist2[j]=true;
else
skiplist2[j]=false;
}
for(k=0;k<no_of_selected_item;k++)
if(skiplist2==true)
{ support[]=unique[i][no_of_selected_item]*(unique[])
}
}
*/
end = tim.getTime();
System.out.println("Execution time is: " + ((double) (end - start) / 1000) + " seconds.");
//All editing Before this line...
if (file_in != null)
file_in.close();
}
catch (IOException e)
{
System.out.println("Error :"+e);
}
finally
{
}
}
}
I want to find time complexity for this algorithm upper bound and lower bound both....Can someone please help.how can we find complexity
