如何产生锯齿状排列的笛卡尔积？ [英] How to generate the cartesian product of a jagged array?

问题描述

我有一些麻烦搞清楚如何产生锯齿状排列的笛卡尔乘积。我用Google搜索周围，但我似乎无法找到一个迭代的语言中implentation。所以我想弄明白自己，但我已经打了一个障碍。让我们界定问题更清楚一点。

I'm having some trouble figuring out how to generate the cartesian product of a jagged array. I have googled around, but i cant seem to find an implentation for a iterative language. So i'm trying to figure it out myself, but i've hit a snag. Lets define the problem a bit clearer

说，我有一个数组的数组看起来像这样

Say i have an array of arrays which looks like this

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} }

编辑：现在这只是一个例子，第一阵列可以包含阵列的动态数，并且每个阵列是动态大小的

edit: Now this is just an example, the first array can contain a dynamic number of arrays, and each array is of dynamic size.

如果x是外数组中元素的数目，而y []是长度为x的动态数组，含有该内数组中元素的数目的元素。然后A的x变成B的Y和B的x是y的乘总和是在A.（没有证明，从例子假设）

If x is the number of elements in the outer array, and y[] is a dynamic array of length x, the elements containing the number of elements in the inner array. Then the x of A becomes the y of B, and the x of B is the multiplicative sum of y's in A. (not proven, assumed from examples)

由于A的x是动态的，该函数必须是递归的。我的继承人尝试。

Since the x of A is dynamic, the function has to be recursive. Heres my try.

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)++;
  }
}

这是据我已经得到了。递归函数建立了一个[​​深度递归]的一种元素的临时数组，则当其在MAXDEPTH，它分配该B，并增加货币迭代，回溯并且选择[深度递归]，等的下一个元素角

This is as far as i have gotten. The recursive function builds up a temporary array of one element of a[depth of recursion], then when its at maxdepth, it assigns that B, and increases Bs iterator, backtracks and selects the next element of a[depth of recursion], et c.

问题存在设计缺陷，我不能找出原因。

The problem being segfaults and i cant figure out why.

推荐答案

这个问题在你分配B.方式你需要把它分配为的下一页末的指针为int数组，然后分配每个元素作为数组的 newy指定的整数。

The problem is in the way you allocate B. You need to allocate it as an array of newx pointers to int, and then allocate each element as an array of newy ints.

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

不过我还是通过迭代求解我的previous答案受不了。

But I still stand by my previous answer of using an iterative solution.

这篇关于如何产生锯齿状排列的笛卡尔积？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！