对数组执行笛卡尔积

Question

我很感兴趣在n个数组上执行笛卡尔积。如果我事先知道数组的数量，我可以编写代码。例如，给定2个数组：

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个数组。有没有办法做到这一点？谢谢！

- ms1013

---

我不是很清楚：你是在问如何编写每个可能的数组对的笛卡尔积吗？例如ab，ac，.... az，bc，bd，... bz等等？ - duffymo

cartesianProduct()：http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Sets.html - goat

这是外积。笛卡尔积只会形成元素的元组而不是将它们相乘。 - starblue

Answer 1

解决这个问题的一种方法是不断通过注意到以下式子将数组数量逐一减少：

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

因此，您可以编写像这样的函数，它计算两个数组的笛卡尔积：

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

现在，您可以使用这个函数将数组对组合成一个包含整体笛卡尔积的单一数组。 伪代码如下:

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：

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

这种方法的问题是它使用与您生成的元素总数成比例的内存，这可能是一个非常庞大的数字！如果您只想逐个打印所有值而不存储它们，有一种更有效的方法。思路是可以开始列出在不同数组中的索引的所有可能组合，然后仅乘以这些位置处的值即可。一种方法是维护一个“索引数组”，其中指出要查看的下一个索引是什么。您可以通过与增加数字相同的方式“递增”数组来从一个索引移动到下一个索引。以下是相关代码：

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 是你有的数组数量，但可能会生成指数级别多的值。

希望这能帮到你！

- templatetypedef

Answer 2

您可以使用递归而非迭代 - 但要注意 - 可能会出现 StackOverflowException 异常。

- Xeon

---

我知道你在说什么解决方案，但如果你还不知道自己想要什么，我认为这个答案帮不了你太多。 - templatetypedef

我怀疑你只有一堆大小为1的集合才会遇到StackOverflowException。即使是大小为2的集合，你使用指数级的内存，但只使用线性的栈空间，所以你很快就会耗尽内存而不是栈。 - Rob Neuhaus