Как сгенерировать декартово произведение зубчатого массива?

Question

У меня возникли проблемы с выяснением, как генерировать декартово произведение зубчатого массива. Я гуглил, но не могу найти смысла для итеративного языка. Так что я пытаюсь понять это сам, но я наткнулся на загадку. Давайте определим проблему немного яснее

скажем, у меня есть массив массивов, который выглядит следующим образом

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: теперь это только пример, первый массив может содержать динамическое количество массивов, и каждый массив имеет динамический размер.

Если x - это количество элементов во внешнем массиве, а y [] - это динамический массив длины x, то есть элементы, содержащие количество элементов во внутреннем массиве. Тогда x из A становится y из B, а x из B является мультипликативной суммой y в A. (не доказано, предполагается из примеров)

Поскольку x из A является динамическим, функция должна быть рекурсивной. Вот моя попытка.

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

Это насколько я получил. Рекурсивная функция создает временный массив из одного элемента [глубины рекурсии], затем, когда она достигает максимальной глубины, она назначает этот B и увеличивает итератор Bs, отслеживает и выбирает следующий элемент [глубины рекурсии], и т. Д. с.

Проблема в том, что это segfaults, и я не могу понять, почему.

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

Но я все еще поддерживаю мой предыдущий ответ об использовании итеративного решения.

Answer 2

Вы начали с того, что не можете найти итеративную реализацию, поэтому в качестве ответа на ваш вопрос я предложу один.

Начните с массива, содержащего столько целых чисел, сколько у вас есть наборов., начиная с них всех в 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 - последний передвесь массив переворачивается снова.