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

Question

У меня возникли проблемы с выяснением того, как создать декартово произведение массива с зубцами. У меня есть googled вокруг, но я наклоняю, кажется, ищут имплантацию для итеративного языка. Поэтому я пытаюсь понять это сам, но я попал в ловушку. Позволяет определить проблему немного яснее

Скажем у меня есть массив массивов, который выглядит как этот

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, элементы, содержащие количество элементов во внутреннем массиве. Тогда x of A становится y of B, а x of B является мультипликативной суммой y в A. (не доказано, взято из примеров)

Поскольку x of 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)++; 
    } 
} 

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

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

Answer 1

Проблема заключается в том, как вы распределяете B. Вам нужно передать его как массив newx указателей на INT, а затем выделить каждый элемент в виде массива Newy Интс.

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 является последним перед весь массив переворачивается снова.