I am trying to find cartesian product of sets(with integer elements)
using Java. I have written a program as shown below.
import java.util.List;
import java.util.ArrayList;
public class SetUtil {
public static ArrayList cross(List sets) {
ArrayList result = new ArrayList();
if (sets.size() == 2) {
for (int i = 0; i < ((Integer[])sets.get(0)).length; i++) {
for (int j = 0; j < ((Integer[])sets.get(1)).length; j++) {
ArrayList al = new ArrayList();
al.add(((Integer[])sets.get(0))[i]);
al.add(((Integer[])sets.get(1))[j]);
result.add(al);
}
}
}
else {
ArrayList temp = cross(sets.subList(0, sets.size() - 1));
Integer[] x = (Integer[])sets.get(sets.size() - 1);
for (int i = 0; i < temp.size(); i++) {
for (int j = 0; j < x.length; j++) {
ArrayList al = new ArrayList();
for (int p = 0; p < ((ArrayList)temp.get(i)).size(); p++) {
al.add(((ArrayList)temp.get(i)).get(p));
}
al.add(x[j]);
result.add(al);
}
}
}
return result;
}
}
Calling program is
--------------------------
Integer[] set1 = {new Integer(1), new Integer(2), new Integer(3)};
Integer[] set2 = {new Integer(4), new Integer(5)};
Integer[] set3 = {new Integer(6), new Integer(7), new Integer(8) , new
Integer(9)};
..more sets
List sets = new ArrayList();
sets.add(set1);
sets.add(set2);
sets.add(set3);
..add more sets
//find cartesian product
ArrayList result = SetUtil.cross(sets);
//print result
for(int i = 0; i < result.size(); i++) {
ArrayList al = (ArrayList)result.get(i);
for (int j = 0; j < al.size(); j++) {
System.out.print(((Integer)al.get(j)).intValue()+" ");
}
System.out.println();
}
The program works fine for small number of sets with low cardinality.
For large number of sets with high cardinality, I get the error
Exception in thread "main" java.lang.OutOfMemoryError
I have tried running the program with options -Xms and -Xmx but the
program still fails..
Can someone please suggest an efficient algorithm for cartesian product
for arbitrarily large number of sets with high cardinality?
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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
