Creating the cartesian product of two lists into a new list in C

Question

I want to create an array that is the cartesian product of two arrays. So for example:

const char *first[] = {"1", "2","3"};
const char *second[] = { "a" , "b" , "c", "e"};

The result is the array:

Cartesian = {"(1,a)","(1,b)","(1,c)",....};

This is what I have for now:

int main(int argc, const char * argv[]) {

    const char *first[] = {"1", "2","3"};
    const char *second[] = { "a" , "b" , "c", "e"};

    int size = sizeof(first) * sizeof(second);

    char *both[size];
    int i=0;

    for (int f=0; f<sizeof(first); f++) {  
       for (int s=0; s<sizeof(second); s++) {
          char *temp[size];
           strcpy(temp[s], "("+first[f]+ ","second[s]+")");
           both[i] = temp;
           i++;
       }
   }
   return 0;
}

Answer 1

The program can look the following way

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

int main( void )
{
    const char *first[] = { "1", "2", "3" };
    const char *second[] = { "a" , "b" , "c", "e" };
    const size_t N = sizeof( first ) / sizeof( *first );
    const size_t M = sizeof( second ) / sizeof( *second );
    char product[N * M][3];

    for ( size_t i = 0; i < N; i++ )
    {
        for ( size_t j = 0; j < M; j++ )
        {
            strcpy( product[i*M + j], first[i] );
            strcat( product[i*M + j], second[j] );
        }
    }

    for ( size_t i = 0; i < N * M; i++ ) printf( "%s ", product[i] );
    printf( "\n" );

    return 0;
}

The program output is

1a 1b 1c 1e 2a 2b 2c 2e 3a 3b 3c 3e 

If you want to enclose each string in parentheses then the program can look like

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

int main( void )
{
    const char *first[] = { "1", "2", "3" };
    const char *second[] = { "a" , "b" , "c", "e" };
    const size_t N = sizeof( first ) / sizeof( *first );
    const size_t M = sizeof( second ) / sizeof( *second );
    char product[N * M][6];

    for ( size_t i = 0; i < N; i++ )
    {
        for ( size_t j = 0; j < M; j++ )
        {
            strcpy( product[i*M + j], "(" );
            strcat( product[i*M + j], first[i] );
            strcat( product[i*M + j], "," );
            strcat( product[i*M + j], second[j] );
            strcat( product[i*M + j], ")" );
        }
    }

    for ( size_t i = 0; i < N * M; i++ ) printf( "%s ", product[i] );
    printf( "\n" );

    return 0;
}

The program output is

(1,a) (1,b) (1,c) (1,e) (2,a) (2,b) (2,c) (2,e) (3,a) (3,b) (3,c) (3,e) 

Also the loops

    for ( size_t i = 0; i < N; i++ )
    {
        for ( size_t j = 0; j < M; j++ )
        {
            strcpy( product[i*M + j], "(" );
            strcat( product[i*M + j], first[i] );
            strcat( product[i*M + j], "," );
            strcat( product[i*M + j], second[j] );
            strcat( product[i*M + j], ")" );
        }
    }

can be written simpler using sprintf (or even snprintf)

for ( size_t i = 0; i < N; i++ )
{
    for ( size_t j = 0; j < M; j++ )
    {
        sprintf( product[i*M + j], "(%s,%s)", first[i], second[j] );
    }
}

Answer 2

Problems in your code:

1. sizeof(first)(and sizeof(second)) gives number of string literals in the array * sizeof(char*). You need to discard the second part. Just divide it by sizeof(char*) or sizeof(*str) as @BLUEPIXY suggested which is the same as sizeof(str[0]):

   int size = (sizeof(first) / sizeof(*first)) * (sizeof(second) / sizeof(*second));
   

2. Your loops:

   for (int f=0; f<sizeof(first); f++)
   for (int s=0; s<sizeof(second); s++)
   

   suffer the same problem. I suggest using

   int size1 = sizeof(first) / sizeof(*first);
   int size2 = sizeof(second) / sizeof(*second)
   
   for (int f=0; f < size1; f++)
   for (int s=0; s < size2; s++)
   

3. Your body of the loop has many problems. Remove everything from it. The following steps show what to do there.

Steps to resolve the problems:

1. You need to allocate memory for char *both[size];. Allocate memory from the body of the loop:

   int i=0;
   
   for (int f=0; f < size1; f++)
   {
       for (int s=0; s < size2; s++)
       {
           both[i] = malloc(strlen(first[f]) + strlen(second[s]) + 4);
           /*Mallocing space for two brackets, a comma, a NUL-terminator and the coordinates*/
           i++; //Increment counter
       }
   }
   

2. strcpy is the wrong function to use here. Use sprintf instead:

   int i=0;
   
   for (int f=0; f < size1; f++)
   {
       for (int s=0; s < size2; s++)
       {
           both[i] = malloc(strlen(first[f]) + strlen(second[s]) + 4);
   
           sprintf(both[i], "(%s,%s)",first[f],second[s]); // Make the string
           i++;
       }
   }
   

3. After the loop, both is populated according to your needs. Print them using:

   for(int j=0; j<i ; j++)
       printf("%s \n",both[j]);
   

4. After its use, free the allocated memory using:

   for(int j=0; j<i ; j++)
       free(both[j]);
   

Fixed program:

#include <stdio.h>
#include <stdlib.h> //For malloc and free
#include <string.h> //For strlen

int main(int argc, const char * argv[]) {

    const char *first[] = {"1", "2","3"};
    const char *second[] = { "a" , "b" , "c", "e"};

    int size = (sizeof(first) / sizeof(*first)) * (sizeof(second) / sizeof(*second));

    char *both[size];
    int i=0;

    int size1 = sizeof(first) / sizeof(*first);
    int size2 = sizeof(second) / sizeof(*second)

    for (int f=0; f < size1; f++)
    {
        for (int s=0; s < size2; s++)
        {
            both[i] = malloc(strlen(first[f]) + strlen(second[s]) + 4);
            sprintf(both[i], "(%s,%s)",first[f],second[s]);
            i++;
        }
    }

    for(int j=0; j<i ; j++)
        printf("%s\n",both[j]);

    for(int j=0; j<i ; j++)
        free(both[j]);

    return 0; //or return(EXIT_SUCCESS);
}

Other notes:

• Check the result of malloc to see if it was successful in allocating memory. malloc returns NULL on failure.
• Checking the result of sprintf is also good, although not neccessary. sprintf returns a negative number on failure.