我有兴趣在 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 个数组。有没有办法我可以做到这一点？谢谢！
解决此问题的一种方法是通过注意以下几点来不断减少数组的数量
A 0 × A 1 × A 2 = (A 0 × A 1 ) × A 2
因此，您可以编写一个像这样的函数，它计算两个数组的笛卡尔积：
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 是您拥有的数组的数量，但会产生可能呈指数级增长的许多值。
希望这可以帮助！
您可以使用递归而不是迭代 - 但请注意 - 可能会发生 StackOverflowException。