Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.5k views
in Technique[技术] by (71.8m points)

java - Perfoming Cartesian product on arrays

I'm interested in performing a Cartesian product on n arrays. I can write the code if I know the number of arrays ahead of time. 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 do not know the number of arrays. I may have 2 arrays, or I may have 100 arrays. Is there a way that I can do this? Thanks!

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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

A0 × A1 × A2 = (A0 × A1) × A2

Consequently, you could write a function like this one, which computes 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 keep combining together pairs of arrays into one single array containing the overall Cartesian product. In pseudocode:

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, as 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 produce. This can be a really huge number! If you just want to print all of the values out one at a time without storing them, there is a more efficient approach. The idea is that you can start listing off all possible combinations of indices in the different arrays, then just go multiply together the values at those positions. One way to do this is to maintain an "index array" saying what the next index to look at is. You can move from one index to the next by "incrementing" the array the same way you would increment a number. Here's some code for that:

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;
    }
}

This uses only O(L) memory, where L is the number of arrays you have, but produces potentially exponentially many values.

Hope this helps!


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...