[algogeeks] Re: To find cartesian product of sets

[Mukul Gandhi]

I experimented with your suggestion 1. Following is the modified
function

public static void cross(List sets) throws Exception {

   if (sets.size() == 2) {
     FileWriter op1 = new FileWriter("temp.txt");
     FileWriter op2 = new FileWriter("out.txt");

     for (int i = 0; i < ((Integer[])sets.get(0)).length; i++) {
         for (int j = 0; j < ((Integer[])sets.get(1)).length; j++) {
           op1.write((((Integer[])sets.get(0))[i]).toString());
           op1.write(" "+(((Integer[])sets.get(1))[j]).toString());
           op1.write("\n");

           op2.write((((Integer[])sets.get(0))[i]).toString());
           op2.write(" "+(((Integer[])sets.get(1))[j]).toString());
           op2.write("\n");
        }
   }

   op1.close();
   op2.close();
 }
 else {
   cross(sets.subList(0, sets.size() - 1));
   Integer[] x = (Integer[])sets.get(sets.size() - 1);

   BufferedReader temp = new BufferedReader(new FileReader("out.txt"));
   FileWriter ot = new FileWriter("temp.txt");
   String l = "";
   while ((l = temp.readLine()) != null) {
     ot.write(l+"\n");
   }
   temp.close();
   ot.close();

   BufferedReader in = new BufferedReader(new FileReader("temp.txt"));
   FileWriter out = new FileWriter("out.txt");

   String line = "";

   while ((line = in.readLine()) != null) {
       for (int j = 0; j < x.length; j++) {
       StringTokenizer st = new StringTokenizer(line," ");
       while (st.hasMoreTokens()) {
         out.write(st.nextToken()+" ");
       }
       out.write(x[j].toString()+"\n");
   }
 }

 in.close();
 out.close();
}

}

Now I don't get OutOfMemoryError error. The method works. I tested with
14 sets, and each set had 5 elements. The resulting file size (out.txt)
is of size 6 GB. The swapping between out.txt and temp.txt takes long
time. The total time taken by the program was about 3 hours.

I am not happy with the output file size and the execution time.

Ideally, I want a solution like your suggestion 2. I just want to
iterate the cartesian product and don't store it anywhere.

I'll be happy if someone could suggest such an algorithm.

Regards,
Mukul


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---