0
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

2
Contributors
1
Reply
14
Views
3 Years
Discussion Span
Last Post by iamthwee
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.