about cartesian product

It's not clear exactly what you're asking: what "information" about the product do you want?

Since a Cartesian product is ordered you could represent a typical element as an ArrayList of the base type. The complete product would then be a Set of ArrayLists of the base type - it would be rather large, and depending on what you are trying to do you might not need to ever form the complete set.

pbrockway2a at 2007-7-12 15:37:46 >

chongo,

To begin with, it looks like your sets have binary strings as elemens, so (unless your binary strings are ever longer than 16 bits) you can use one integer to represent each element. For instance, the element 01101 is equivalent to 0000000000001101, which is 13 in base two, so it will be a 13 in the set. (All I'm saying is, you don't need to use a string representation.)

The sets themselves are probably most easily stored as arrays of ints. This gives us a notion of order that might be useful for calculating the cartesian product, and is quick and easy to implement.

For the product, I would not even bother calculating the whole thing at once unless you need acces to all of its elements more than a few times. If you represent your existing sets by arrays, you have constant-time random access to the elements in a definite order, so you could just write a method that returns specific elements of the Cartesian product. This will effectively give you access to elements in the Cartesian product in O(n) time. For an example of such a method (check this code before using it):

public static int[] getCartesianElement(int[][] sets, int[] coordinates) {

if (sets.length != coordinates.length)

throw new IllegalArgumentException("lengths do not match");

int[] element = new int[sets.length];

for (int i = 0; i < sets.length; i++)

element[i] = sets[i][coordinates];

return element;

}

or, if you know you're using only one set in the product,

public static int[] getCartesianElement(int[] set, int[] coordinates) {

int[] element = new int[coordinates.length];

for (int i = 0; i < coordintates.length; i++)

element[i] = set[coordinates];

return element;

}

I used the name "coordinates" for the int[] specifying which element we want because you can think of the elements of the product as occupying points in n-space, with the coordinates resulting form the handy ordering imposed by the array representation. In the second method, the number of operands is implicit in the length of coordinates.

If you really want to generate the whole product, the code above could be easily adapted.

ProGrapea at 2007-7-12 15:37:46 >