de itertools.product Python en C

Question

Il y a une fonction en Python qui fonctionne de cette façon:

itertools.product("abc", repeat = 2) 

renvoie les éléments suivants:

("a", "a") 
("a", "b") 
("a", "c") 
("b", "a") 
("b", "b") 
("b", "c") 
("c", "a") 
("c", "b") 
("c", "c") 

Changer la variable de répétition changera le nombre d'éléments reviennent dans un tuple. Comment cela peut-il être écrit en C pour renvoyer un tableau de tableaux de caractères? (Un tableau de chaînes)

MISE À JOUR: J'ai maintenant cette fonction que j'ai écrit:

void cartesian(char *a, int al, char *b, int bl){ 
    int i, j; 
    char c[al * bl][2]; 
    for(i = 0; i < al; i++){ 
     for(j = 0; j < bl; j++){ 
      c[(i * bl) + j][0] = *(a + i); 
      c[(i * bl) + j][1] = *(b + j); 
      printf("%c%c\n", *(a + i), *(b + j)); 
     } 
    } 
} 

int main(){ 
    char a[] = "abc"; 
    char b[] = "ab"; 
    cartesian(a, strlen(a), b, strlen(b)); 
    return 0; 
} 

Comment puis-je changer cette fonction de sorte qu'il peut prendre dans un tableau de de tableaux de l'omble chevalier et rendre le produit cartésien ? Les tableaux peuvent contenir un certain nombre de caractères et il pourrait y avoir un certain nombre de tableaux

La fonction devrait ressembler à:

void cartesian(char *a, int l){ 
    /*Do cartesian*/ 
} 

Exemple tableau:

[ 
    ['a', 'b', 'c', '\0'], 
    ['a', 'b', 'c', '\0'], 
    ['a', 'b', 'c', '\0'] 
] 

(nulls inclus pour travailler la longueur des tableaux) devrait produire

[ 
    ['a', 'a', 'a'], 
    ['a', 'a', 'b'], 
    ['a', 'a', 'c'], 
    ['a', 'b', 'a'], 
    ['a', 'b', 'b'], 
    ['a', 'b', 'c'], 
    ['a', 'c', 'a'], 
    ['a', 'c', 'b'], 
    ['a', 'c', 'c'], 
    ['b', 'a', 'a'], 
    ['b', 'a', 'b'], 
    ['b', 'a', 'c'], 
    ['b', 'b', 'a'], 
    ['b', 'b', 'b'], 
    ['b', 'b', 'c'], 
    ['b', 'c', 'a'], 
    ['b', 'c', 'b'], 
    ['b', 'c', 'c'], 
    ['c', 'a', 'a'], 
    ['c', 'a', 'b'], 
    ['c', 'a', 'c'], 
    ['c', 'b', 'a'], 
    ['c', 'b', 'b'], 
    ['c', 'b', 'c'], 
    ['c', 'c', 'a'], 
    ['c', 'c', 'b'], 
    ['c', 'c', 'c'], 
] 

Answer 1

Voici une implémentation C de produits cartésiens selon vos spécifications. Notez cependant que l'argument est char **a, pas char *a car il s'agit d'un tableau de chaînes.

C'est une variation sur une version previous answer.

void cartesian(char **a, unsigned int l) 
    { 
     unsigned int *indices = calloc(l, sizeof(int)); 
     unsigned int changed; 
     do { 
      unsigned int finished = 0; 
      unsigned int i; 
      changed = 0; 
      /* Print the current tuple */ 
      for (i = 0; i < l; i++) { 
       putchar(a[i][indices[i]]); 
      } 
      putchar('\n'); 
      /* Loop over the arrays in reverse order */ 
      for (i = l - 1; !changed && !finished; i--) { 
       /* Increment */ 
       indices[i]++; 
       if (a[i][indices[i]]) { 
        /* We moved to the next character */ 
        changed = 1; 
       } 
       else { 
        /* End of string, so roll over */ 
        indices[i] = 0; 
       } 
       finished = i == 0; 
      } 
     } while (changed); 
     free(indices); 
    } 

Answer 2

Le C suivant programme crée toutes les permutations possibles de "abc".

#include <stdio.h> 
#include <string.h> 

/* Function to swap values at two pointers */ 
void swap(char *x, char *y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 

void permute(char *a, int l, int r) 
{ 
    int i; 
    if (l == r) 
    printf("%s\n", a); 
    else 
    { 
     for (i = l; i <= r; i++) 
     { 
      swap((a+l), (a+i)); 
      permute(a, l+1, r); 
      swap((a+l), (a+i)); //backtrack 
     } 
    } 
} 

int main() 
{ 
    char str[] = "abc"; 
    int n = strlen(str); 
    permute(str, 0, n-1); 
    return 0; 
} 

Il existe probablement un moyen encore plus rapide de coder ceci. Runtime O (n * n!). J'ai seulement remarqué plus tard que vous demandiez le produit cartésien. Mais plusieurs entrées de débordement de pile peuvent être trouvées avec des requêtes similaires. Generate the Cartesian Product of 2 vector<string>s In-Place?