Perfoming对数组笛卡尔乘积 [英] Perfoming Cartesian product on arrays

问题描述

我感兴趣的n个阵列进行笛卡尔乘积。我可以写code，如果我知道的数组数的时间提前。例如，给定2数组：​​

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

的问题是，在运行时，不知阵列的数目。我可能有2个阵列，或者我可能有100个阵列。有没有一种方法，我可以做到这一点？谢谢！

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!

推荐答案

要解决这个问题的方法之一是通过观察不断降低的时间阵列之一的数

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

A <子> 0 ＆倍; A <子> 1 ＆倍; A ₂ =（A <子> 0 ＆倍; A <子> 1 ）次; A ₂

A₀ × A₁ × A₂ = (A₀ × A₁) × A₂

因此​​，你可以写像这样的，它计算两个数组的笛卡儿积函数：

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

现在，您可以使用此功能，以保持对阵列组合成包含整个笛卡尔乘积一个单一的阵列。在伪code：

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.

此外，由于实际的Java：

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();

使用这种方法的问题是，它使用存储器成正比你产生元件的总数。这可能是一个非常庞大的数字！如果你只是想在一个时间没有将其存储到打印所有的价值观出一个，还有一个更有效的方法。我们的想法是，你可以启动上市关在不同的阵列指数的所有可能的组合，然后随便去乘一起在这些位置的值。这样做的一个办法是维持一个索引数组的说法怎么看接下来的索引处。可从一个索引的递增的阵列，你会递增一个号码相同的方式移动到下一个。下面是一些code为：

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

这仅使用O（L）的内存，其中L是你有阵列的数量，但会产生潜在的成倍多个值。

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

希望这有助于！

这篇关于Perfoming对数组笛卡尔乘积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！