我遇到了一些困难,不知道如何生成一个嵌套数组的笛卡尔积。我已经在谷歌上搜索了许多,但似乎没有迭代语言的实现。因此,我正在尝试自己解决问题,但我遇到了一些问题。让我们更清楚地定义一下这个问题。
假设我有一个数组,它看起来像这样
A = { {1}, {2, 3}, {4, 5, 6} }
我该如何从那里开始?
B = { {1, 2, 4}, {1, 2, 5}, {1, 2, 6}, {1, 3, 4}, {1, 3, 5}, {1, 3, 6} }
编辑:现在这只是一个例子,第一个数组可以包含动态数量的数组,每个数组的大小也是动态的。
假设x是外部数组中元素的数量,y[]是长度为x的动态数组,其中包含内部数组的元素数量。那么A的x变成了B的y,B的x是A中y的乘积总和(未经证明,从示例中推测)。
由于A的x是动态的,函数必须是递归的。这是我的尝试。
int** cartesian (int** A, int x, int* y, int* newx, int* newy) {
*newy = x;
*newx = 1;
for (int i = 0; i < x; i++)
*newx *= y[i];
int** B = malloc(sizeof(int) * *newx * *newy);
int xi = 0;
int* tmp_prod = malloc(sizeof(int) * x);
recurse(x, 0, y, A, &xi, tmp_prod, B);
free(tmp_prod);
return B;
}
void recurse(int x, int xi, int* y, int** A, int* newx, int* temp_inner, int** B) {
if (xi < x) {
for (int i = 0; i < y[xi]; i++) {
temp_inner[xi] = A[xi][i];
recurse(x, xi + 1, y, A, newx, temp_inner, B);
}
} else {
for (int i = 0; i < x; i++) {
B[*newx][i] = temp_inner[i];
}
(*newx)++;
}
}
这是我已经得到的结果。递归函数建立一个临时数组,其中包含a[递归深度]的一个元素,当它达到最大深度时,它将其分配给B,并增加Bs迭代器,然后回溯并选择a[递归深度]的下一个元素,以此类推。
问题是出现了segfaults,我无法弄清原因。
B = { {1, 2, 4}, {1, 2, 5}, {1, 2, 6}, {1, 3, 4}, {1, 3, 5}, {1, 3, 6} }
,请注意最后两个元组中间元素的变化。 - Arun