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

如何能做到这一点正确明知组阵列可以具有可变的大小？

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 

产生以下输出：

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';