C Multiple arrays permutations algorithm

Question

I'm trying to write a program that generates permutations upon a list of words stored into several arrays. For example, my program asks for 2 groups of words like this :

words #1: abc def ghi
words #2: 123 456

What i'm trying to have is this output:

abc 123 | abc 456 | def 123 | def 456 | ghi 123 | ghi 456

Or:

123 abc | 123 def | 123 ghi | 456 abc | 456 def | 456 ghi

The order doesn't matter.

I'd possibly make the group of words array with a non-fixed size. Then the input would be:

words #1: abc def ghi
words #2: 123 456
words #3: ** --

And the output:

abc 123 ** | abc 123 -- | abc 456 ** | abc 456 -- | def 123 ** | def 123 -- | def 456 ** | def 456 -- | ghi 123 ** | ghi 123 -- | ghi 456 ** | ghi 456 --

I think I had to consider using a recursive function but i'm a bit confused. Here is what I've written :

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

typedef struct permut_word_s {
    char *str;
} permut_word_t;

typedef struct permut_group_s {
    permut_word_t *words;
    int nb_words;
} permut_group_t;

static int split(char *str,
                 char *token,
                 permut_group_t *g) {
    permut_word_t *a = NULL;
    permut_word_t *t = NULL;
    char *p = NULL;
    int nbw = 0;
    int l = 0;

    if(!str || !token || !g) {
        return -1;
    }

    p = strtok(str, token);

    while(p != NULL) {
        if(!(t = realloc(a, (nbw + 1) * sizeof(permut_word_t)))) {
            return -1;
        }
        if(!(t[nbw].str = malloc(strlen(p) + 1))) {
            return -1;
        }
        memset(t[nbw].str, 0, strlen(p) + 1);
        if(!(strncpy(t[nbw].str, p, strlen(p)))) {
            return -1;
        }
        nbw++;
        p = strtok(NULL, token);
        a = t;
    }

    g->words = a;
    g->nb_words = nbw;

    return 0;
}

void word_free(permut_word_t *w) {
    if(!w) {
        return;
    }

    if(w->str) {
        free(w->str);
    }

    return;
}

void group_free(permut_group_t *g) {
    int i = 0;

    if(!g) {
        return;
    }

    for(; i < g->nb_words; i++) {
        if(&g->words[i]) {
            word_free(&g->words[i]);
        }
    }

    free(g->words);
    return;
}

void permut(permut_group_t *g,
            int cur,
            int len) {
    int i = 0;
    int j = 0;

    if(cur == len) {
        return;
    }

    for(i = cur; i < len; i++) {
        for(j = 0; j < g[cur].nb_words; j++) {
            printf("%s ", g[cur].words[j].str);
        }
        permut(g, cur + 1, len);
    }
}

int main(int argc, char **argv) {
    char buf[1024] = { 0 };
    permut_group_t *groups = NULL;
    int len = 0;

    (void)argc;
    (void)argv;

    if(!(groups = malloc(2 * sizeof(permut_group_t)))) {
        return -1;
    }

    fprintf(stdout, "words #1: ");
    fgets(buf, 1024, stdin);
    split(buf, " ", &groups[0]);
    len++;

    fprintf(stdout, "words #2: ");
    fgets(buf, 1024, stdin);
    split(buf, " ", &groups[1]);
    len++;

    permut(&groups[0], 0, len);

    group_free(&groups[0]);
    group_free(&groups[1]);
    free(groups);

    return 0;
}

How can do it correctly knowing that the groups array may have a variable size?

Answer 1

Try the following:

void permut(permut_group_t *g,
            int cur,
            int len, char *result=NULL) {
    int j = 0;

    if(cur == len) {
        printf("%s\n", result);
        return;
    }

    for(j = 0; j < g[cur].nb_words; j++) {
        char nextLine[200];
        if (cur==0)
            strncpy (nextLine, g[cur].words[j].str, 200);
        else
            snprintf (nextLine, 200, "%s;%s", result, g[cur].words[j].str);

        permut(g, cur + 1, len, nextLine);
    }
}

The following input

words #1: AB CD
words #2: 11 22 33

produces then the following output:

AB;11
AB;22
AB;33
CD;11
CD;22
CD;33

The trick is that when collecting the results, intermediately achieved combinations have to be kept and passed to the next level. Therefore, signature of function permut has been extended by an (optional) parameter char* result, which serves as "memory" for these intermediate (or final) combinations.

The signature of the permutation function is now permut(permut_group_t *g, int cur, int len, char *result=NULL); from function main, you can keep your call permut(&groups[0], 0, len) as is, because optional parameter result can be omitted when parameter cur is 0;

Note that I extended also function split in order to strip any trailing new lines, such that these new lines do not get copied into the results:

char *newLine = strrchr(str, '\n');
if (newLine)
    *newLine = '\0';