3

我在弄清楚如何生成锯齿状数组的笛卡尔积时遇到了一些麻烦。我已经用谷歌搜索了，但我似乎找不到迭代语言的实现。所以我试图自己弄清楚，但我遇到了一个障碍。让我们更清楚地定义问题

假设我有一个看起来像这样的数组数组

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 是 y 在 A 中的乘法和。（未证明，从示例中假设）

由于 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[递归深度]的下一个元素，等C。

问题是段错误，我不知道为什么。

4

2 回答 2

1

您首先说您找不到迭代实现，因此作为对您问题的一种回答，我将提供一个。

从一个包含与集合一样多的整数的数组开始，它们都从 0 开始。每个整数代表一个集合。

const unsigned int x = 3;
unsigned int *ar = calloc(x, sizeof(unsigned int));

现在，向上计数，就好像你的数组是一个里程表，但是当每个数字达到相应集合中的元素数量时，每个数字都会滚动。

然后，您可以使用数组中的索引从集合中读取元素：

{0, 0, 0} = {1, 2, 4}
{0, 0, 1} = {1, 2, 5}
...
{0, 1, 2} = {1, 3, 6}

而 0, 1, 2 是整个数组再次翻转之前的最后一个。

于 2010-10-24T13:27:00.517 回答
1

问题在于分配 B 的方式。您需要将其分配为指向 int 的newx指针数组，然后将每个元素分配为newy int 数组。

int** B = malloc(sizeof(int*) * *newx);
for (unsigned int i = 0 ; i < *newx; i++) {
   B[i] = malloc(sizeof(int) * *newy);
}

但我仍然坚持我之前使用迭代解决方案的答案。

于 2010-10-24T17:59:46.960 回答