Cartesian Product of n-sets in C

Question

I am writing a C program that should print the Cartesian product of n sets, where the elements of each set are the line of text in one file, and the names of the n files are passed as command-line arguments. So far I managed to read every line into matrix of strings. However I cannot wrap my head around how to write the algorithm for printing the product.

Here is what I have so far:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LSIZ 128
#define RSIZ 10
int main(int argc, char *argv[])
{
    char input[LSIZ];
    int n = argc;
    char *sets[argc - 1][RSIZ];
    int i = 0;
    int j = 0;
    int y = 1;
    FILE *file = NULL;
    if (argc == 1)
    {
        printf("nofiles");
    }
    else
    {
        while (--argc > 0)
        {
            if ((file = fopen(argv[y], "r")) == NULL)
            {
                printf("cat: failed to open %s\n", *argv);
                return 1;
            }
            else
            {

                for (j = 0; j < RSIZ && fgets(input, sizeof(input), file); ++j)
                {
                    int lineLen = strlen(input) + 1;
                    sets[i][j] = strncpy(malloc(lineLen), input, lineLen);
                }

                fclose(file);
                j = 0;
            }
            i++;
            y++;
        }
    }
    return 0;
 }

Answer 1

You can implement Cartesian products with an odometer-like counter:

• Set all current items to the first items in each list.
• Process the current state, e.g. print it.
• Advance the first list. If you reach the end, reset the state to the beginning of that list and advance the next list and so on. If you reach the end of the last list, you are done.

So assuming that you have read the information from the files into NULL terminated lists of strings, you could do the following:

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

int main(int argc, char *argv[])
{
    const char *adj1[] = {"little", "big", "huge", NULL};
    const char *adj2[] = {"red", "yellow", "grey", "orange", NULL};
    const char *noun[] = {"house", "car", NULL};
    
    const char **list[3] = {adj1, adj2, noun};
    const char **curr[3];
    
    unsigned n = sizeof(list) / sizeof(*list);
    unsigned count = 0;
    bool done = false;
    
    for (unsigned i = 0; i < n; i++) {
        curr[i] = list[i];
    }
    
    while (!done) {
        unsigned i = 0;

        printf("%s %s %s\n", *curr[0], *curr[1], *curr[2]);
        count++;

        curr[i]++;

        while (*curr[i] == NULL) {
            curr[i] = list[i];      // back to beginning
            i++;                    // move to next list
            
            if (i == n) {           // stop when the last list is exhausted
                done = true;
                break;
            }

            curr[i]++;              // ... and increment that
        }      
    }
    
    printf("%u combinations.\n", count);

    return 0;
}

This approach is not limited to three lists. (If you know exactly how many lists you have, you could use nested loops, of course.)