Comment générer le produit cartésien d’un tableau dentelé?

J’ai du mal à comprendre comment générer le produit cartésien d’un tableau irrégulier. J’ai cherché sur Google, mais je n’arrive pas à trouver une implémentation pour un langage itératif. Donc, j’essaie de comprendre moi-même, mais j’ai un problème. Permet de définir le problème un peu plus clair

Disons que j’ai un tableau de tableaux qui ressemble à ceci

A = { {1}, {2, 3}, {4, 5, 6} } 

comment puis-je aller de cela à

 B = { {1, 2, 4}, {1, 2, 5}, {1, 2, 6}, {1, 3, 4}, {1, 3, 5}, {1, 3, 6} } 

edit: Maintenant, ceci est juste un exemple, le premier tableau peut contenir un nombre dynamic de tableaux et chaque tableau a une taille dynamic.

Si x est le nombre d’éléments dans le tableau externe et y [] est un tableau dynamic de longueur x, les éléments contenant le nombre d’éléments dans le tableau interne. Alors le x de A devient le y de B, et le x de B est la sum multiplicative de y en A. (non prouvé, supposé à partir d’exemples)

Comme le x de A est dynamic, la fonction doit être récursive. Heres mon essai.

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

Ceci est aussi loin que je l’ai eu. La fonction récursive construit un tableau temporaire d’un élément d’une [profondeur de récursion], puis, lorsqu’elle est à maxdepth, elle atsortingbue ce B, et augmente l’iterator B, le retour en arrière et la sélection de l’élément suivant d’une [profondeur de récursion], et c.

Le problème étant les segfaults et je ne peux pas comprendre pourquoi.

Le problème réside dans la façon dont vous allouez B. Vous devez l’affecter en tant que tableau de pointeurs newx à int, puis allouer chaque élément en tant que tableau de newy ints.

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

Mais je rest fidèle à ma réponse précédente consistant à utiliser une solution itérative.

Vous avez commencé par dire que vous ne pouviez pas trouver d’implémentation itérative. Par conséquent, pour répondre à votre question, je vais en proposer une.

Commencez avec un tableau contenant autant d’entiers que vous avez d’ensembles, en commençant par 0. Chaque entier représente un ensemble.

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

Maintenant, comptez vers le haut comme si votre tableau était un compteur kilomésortingque, mais chaque chiffre étant inversé lorsqu’il atteint le nombre d’éléments de l’ensemble correspondant.

Vous pouvez ensuite lire les éléments en les tirant des ensembles en utilisant l’index de votre tableau:

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

Et 0, 1, 2 est le dernier avant que tout le tableau ne se répète.