Difficulties when attempting to create the Cartesian product of a pointer to char pointer

Question

As input I have a pointer to char pointer containing:

{"ab", "cd"}

As output I need to create the following Cartesian product:

{"abab", "abcd", "cdab", "cdcd"}

I created a function that receives "ab, cd" and a pointer to char pointer that is meant to hold the resulting set. Although everything seems to be working fine inside the function, once it gets exited, my output remains empty. I suppose I'm doing something wrong during the concatenation but I'm not sure what.

This is how my code looks like:

#include <stdio.h>

void Permute(char**, int, char**);

main() {
    // my input
    int words = 2;
    char **input;
    input = malloc(sizeof(char*) * words);
    input[0] = "ab";
    input[1] = "cd";

    // compute how much memory we need
    char **output;
    output = malloc(sizeof(char*) * (words * 2));

    // start permutation
    Permute(input, words, output);

    // show output
    int i = 0;
    for(i = 0; i < (words * 2); ++i) {
        // should print: {abcd, abab, cdab, cdcd} 
        // but nothing gets printed
        printf("%s\n", output[i]); 
    }
    free(input);
    free(output);
}

void Permute(char **input, int words, char **output){
    int i = 0, j = 0, k = 0;
    char str[5];
    for(i = 0; i < words; ++i) {
        for(j = 0; j < words; ++j) {
            strcpy (str, input[i]);
            strcat (str, input[j]);
            output[k] = str;
            // at this point concatenation is printed correctly
            printf("%s\n", output[k]); correctly
            ++k;
        }
    }
}

EDIT

Thanks to Goz's comment I updated my function. Now, a pointer to char gets allocated, is pointed to the concatenation and is then stored inside output[k]. This way no data is lost when exciting the funcion:

void Permute(char **input, int words, char **output){
    int i = 0, j = 0, k = 0;
    char *p;
    for(i = 0; i < words; ++i) {
        for(j = 0; j < words; ++j) {
            p = malloc(sizeof(char*) * 5);
            strcpy(p, input[i]);
            strcat (p, input[j]);
            output[k] = p;
            printf("%d %s \n", k, output[k]); 
            ++k;
        }
    }
}

EDIT

The buffer holding the result gets allocated before passing it over to the Permute function:

    // compute how much memory we need
    // allocate space for 4 pointers to char
    char **output = malloc(sizeof(char*) * 4); 
    int i = 0;
    // pre-allocate space for every pointer 
    for(i = 0; i++; i < 4 )
       output[i] = malloc( sizeof( char ) * 5 ); to char

EDIT

Free all memory pointed to by char pointer before cleaning up the pointer to char pointer:

    // free memory
    for(i = 0; i++; i < 4 )
       free( output[i] );
    free(output);

    for(i = 0; i++; i < 2 )
       free(input[i]);
    free(input);

Answer 1

char str[5]; in Permute is on the stack and lost after you exit Permute. output[k] will point to an undefined place once you exit Permute.

Answer 2

There are a couple of issues. Firstly you allocate a char*. You then assign it to a char** and expect it to have 2 dimensionality. It doesn't. You'd need to malloc a set of char* pointers (4 * whatever your pointer size is ... ie sizeof( char* )) then malloc 5 bytes for each of those pointers.

Furthermore in Permute you overwrite the pointer value with the pointer to str (which doesn't exist outside the function). You ought to be strcpy'ing the contents of str to output[k].

In answer to the comment: Yes that will work but it would be advisable to allocate the buffer before you go into the loop.

ie

char** ptr = malloc( sizeof( char* ) * 4 );
for( int i = 0; i++; i < 4 )
{
   ptr[i] = malloc( sizeof( char ) * 4 ); // sizeof( char ) == 1 but its a good habit to get into.
}

Then as said before strcpy the temporary array into the relevant char* array.

Furthermore remember that when you free the memory you need to do the opposite of the loop above. ie dealloc the 4 individual arrays and then dealloc the array of pointers. ie:

for( int i = 0; i++; i < 4 )
{
   free( ptr[i] );
}
free( ptr );

ie all 5 occasions malloc is called are met with a corresponding free. If you free the array of ptr first you cannot guarantee that the memory is valid. Therefore the 4 pointers stored in that array may no longer be valid. So free them first then the array of pointers.

Answer 3

output = malloc(sizeof(char*) * (words * 2));

Ok, you created output[0], output[1], ... but what are their values?

output[0] is a char * ... where does it point to?

And you cannot copy the address of a local variable in Permute (str) to output. That object ceases to exist once the function returns.