如何生成一个不规则数组的笛卡尔积？

Question

如何生成一个不规则数组的笛卡尔积？

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是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，我无法弄清原因。

- solenskiner

1

我认为你想要的是 B = { {1, 2, 4}, {1, 2, 5}, {1, 2, 6}, {1, 3, 4}, {1, 3, 5}, {1, 3, 6} }，请注意最后两个元组中间元素的变化。 - Arun

哦，是的。当然。我在帖子中进行了更改。谢谢！ - solenskiner

你从哪里得到这个问题陈述的？ - N 1.1

我在自己正在开发的程序中遇到了这个问题。当我记录下我的问题简化版本时犯了一个错误。不过，我不确定这个问题是否是解决我更大问题的正确方案。 - solenskiner

请您能否详细解释一下您的意思？根据我对集合论的理解，我想要做的是笛卡尔积（只是入门级大学课程）。不幸的是，我并不是指您所说的无序n元组，但我确实希望输出的每个内部数组的第一个元素来自输入的第一个数组。 - solenskiner

2个回答

1

问题出在你分配B的方式上。你需要将其分配为一个包含newx个指向int的指针的数组，然后分配每个元素为一个包含newy个int的数组。

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

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

- user325117

哇，太感谢了！它立即就起作用了！:D 是的，这样做更节约资源，概念上也更简单。我明天会试一下。 - solenskiner

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user325117 · Accepted Answer

你一开始说找不到迭代实现的方法，所以作为对你问题的回答，我提供一个。

从包含与你拥有的集合数量相同的整数的数组开始，每个整数都从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 是整个数组再次翻转之前的最后一个。