How to generate the cartesian product of a jagged array?

Question

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

how do i go from that to

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.

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)

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

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.

Answer 1

You began by saying that you can't find an iterative implementation, so as a kind of answer to your question I'll offer one.

Start with an array containing as many integers as you have sets, beginning with them all at 0. Each integer represents one set.

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

Now, count upwards as if your array was an odometer, but with each digit rolling over when it reaches the number of elements in the corresponding set.

You can then read off the elements by taking them from the sets using the index in your array:

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

And 0, 1, 2 is the last one before the whole array rolls over again.

Answer 2

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

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