C语言多数组排列算法

Question

我将尝试编写一个程序，可以在存储在多个数组中的单词列表上生成排列组合。例如，我的程序会这样询问2组单词：

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

我希望你能够将其翻译成以下输出：

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

或者：

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

顺序不重要。

我可能会使用一个非固定大小的单词数组。那么输入将是：

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

输出结果：

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

我认为我需要考虑使用递归函数，但是有些困惑。

以下是我写的代码：

#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;
}

如果groups数组的大小是可变的，应该如何正确地执行？

- Lazao

---

那看起来像是笛卡尔积，而不是排列。 - Eli Korvigo

@EliKorvigo 是的，那是真的。我猜它们都属于组合数学，只是不同的应用。 - RoadRunner

我写这篇文章是因为标题有些令人困惑。在某些时候，人们可能会搜索与排列相关的内容，然后最终发现这里的内容并不相关。同时，那些寻找产品实现方案的人也无法找到你的解决方案。这是从社区角度来看有用性的问题。 - Eli Korvigo

Answer 1

尝试以下操作：

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);
    }
}

以下输入

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

技巧在于收集结果时，需要保留并传递中间得到的组合到下一层。因此，函数permut的签名已经通过一个（可选）参数char* result进行了扩展，它用作这些中间（或最终）组合的“内存”。

排列函数的签名现在是permut(permut_group_t *g, int cur, int len, char *result=NULL)；从函数main，您可以像之前一样调用permut(&groups[0], 0, len)，因为当参数cur为0时，可选参数result可以省略；

请注意，我还扩展了函数split，以便去除任何尾随换行符，这样这些换行符就不会被复制到结果中：

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

- Stephan Lechner