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