在阵列上绘制笛卡尔积

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个阵列.有没有办法可以做到这一点？谢谢!

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是您拥有的数组的数量,但可能会产生指数级的多个值.

希望这可以帮助!