Perforation of a Cartesian product on arrays

Question

I am interested in performing a Cartesian product on n arrays. I can write code if I know the number of arrays in advance. For example, given 2 arrays:

int[] a = new int[]{1,2,3}; int[] b = new int[]{1,2,3}; for(int i=0; i<=a.length; i++){ for(int j=0; j<=b.length; j++){ System.out.println(a[i]*b[j]); } } 

The problem is that at runtime I don't know the number of arrays. I can have 2 arrays, or I can have 100 arrays. Is there a way I can do this? Thanks!

Answer 1

One way to solve this problem is to continuously reduce the number of arrays one at a time, noting that

A ₀ x times A ₁ x A ₂ = (A ₀ x A ₁ ) x A <sub> 2sub>

Therefore, you can write a function that calculates the Cartesian product of two arrays:

 int[] cartesianProduct(int[] one, int[] two) { int[] result = new int[one.length * two.length]; int index = 0; for (int v1: one) { for (int v2: two) { result[index] = v1 * v2; index++; } } return result; } 

Now you can use this function to combine pairs of arrays into one array containing a common Cartesian product. In pseudo code:

 While there is more than one array left: Remove two arrays. Compute their Cartesian product. Add that array back into the list. Output the last array. 

And, like actual Java:

 Queue<int[]> worklist; /* fill the worklist with your arrays; error if there are no arrays. */ while (worklist.size() > 1) { int[] first = worklist.remove(); int[] second = worklist.remove(); worklist.add(cartesianProduct(first, second)); } /* Obtain the result. */ int[] result = worklist.remove(); 

The problem with this approach is that it uses memory proportional to the total number of elements you create. It can be a really huge amount! If you just want to print all the values ​​one at a time without saving them, there is a more efficient approach. The idea is that you can start listing all the possible combinations of indices in different arrays, and then just multiply the values ​​at these positions. One way to do this is to maintain an "index array", indicating that the next index to view. You can move from one index to the next by "increasing" the array in the same way as you increase the number. Here is the code for this:

 int[] indexArray = new int[arrays.length]; mainLoop: while (true) { /* Compute this entry. */ int result = 1; for (int i = 0; i < arrays.length; i++) { result *= arrays[i][indexArray[i]] } System.out.println(result); /* Increment the index array. */ int index = 0; while (true) { /* See if we can bump this array index to the next value. If so, great! * We're done. */ indexArray[index]++; if (indexArray[index] < arrays[i].length) break; /* Otherwise, overflow has occurred. If this is the very last array, we're * done. */ indexArray[index] = 0; index ++; if (index == indexArray.length) break mainLoop; } } 

In this case, only O (L) memory is used, where L is the number of arrays that you have, but give potentially exponentially many values.

Hope this helps!

Answer 2

You can use recursion instead of iteration, but don't look - a StackOverflowException may occur.