更有效的上市组合方式

Question

最近我回答了'如何在这里得到插入数据类型的数组的所有可能组合的许多重复问题之一。我的回答是：

#include <stdio.h> 

int main() 
{ 
    /* String for combos to be enumerated */ 
    char set[4] = { 'a', 'b', 'c', 'd' }; 
    /* Length of the array */ 
    int setLength = 4, a, b, c; 

    /* This will print all combos that have 1 value. E.g. A, B, C, D */ 
    for (a = 0; a < setLength; a++) 
    { 
     printf("%c : ", set[a]); 
    } 

    /* This will give the 1st value of the combo */ 
    for (a = 0; a < setLength; a++) 
    { 
     /* This will give the 2nd value. Resulting in combos with a length of 2 */ 
     for (b = 0; b < setLength; b++)   
     { 
      printf("%c%c : ", set[a], set[b]); 
     } 
    } 

    /* 1st value */ 
    for (a = 0; a < setLength; a++) 
    { 
     /* 2nd value */ 
     for (b = 0; b < setLength; b++) 
     { 
      /* 3rd value */ 
      for (c = 0; c < setLength; c++) 
      { 
       printf("%c%c%c : ", set[a], set[b], set[c]); 
      } 
     } 
    } 

    /* To continue with longer combos simply add more and more for loops */ 
    printf("\n"); 
    return 0; 
} 

然而，当我看着其他回答这个问题，他们都参与了内建的功能从语言例如C＃。因此，我的问题是：我的答案是否正确或可靠，如果没有内置函数，那么这样做会更有效。

Answer 1

您可以使用简单算法与回溯 - 一种技术，它允许您使用以前计算的一部分来获得更多值。

下面的代码：

void print_comb_rec(char* values, int n, int length, char* helper) 
{ 
    int i; 

    if (length == 0) 
    { 
     printf("%s : ", helper); 
     return; 
    } 

    for (i = 0; i < n; i++) 
    { 
     helper[length - 1] = values[i]; 
     print_comb_rec(values, n, length - 1, helper); 
    } 
} 

void print_comb(char* values, int n, int length) 
{ 
    char* helper = malloc(sizeof(char) * (length + 1)); 
    int i; 

    helper[length] = '\0'; 
    print_comb_rec(values, n, length, helper); 

    free(helper); 
} 

用法：使用功能print_comb。它需要排列的值，数组的长度和组合的长度。通过使用它，您可以获得给定长度的结果。

请注意，对于给定的n，可能组合的数目会按指数递增（即它是O(n^length)）。至于任何递归算法，也有可能使用它来用完堆栈的内存。

Answer 2

我需要一个比一个评论更多的空间，所以把它放在这里：

对此代码：

for (a = 0; a < setLength; a++) 
{ 
    /* This will give the 2nd value. 
    * Resulting in combos with a length of 2 
    */ 
    for (b = 0; b < setLength; b++) 
    { 
     printf("%c%c : ", set[a], set[b]); 
    } 
} 

会导致不正确的输出连击，如：

aa 
bb 
cc 
dd 

哪些不是有效的组合

此编号：

/* 1st value */ 
for (a = 0; a < setLength; a++) 
{ 
    /* 2nd value */ 
    for (b = 0; b < setLength; b++) 
    { 
     /* 3rd value */ 
     for (c = 0; c < setLength; c++) 
     { 
      printf("%c%c%c : ", set[a], set[b], set[c]); 
     } 
    } 
} 

将导致输出连击，如：

aaa 
aab 
aac 
aad 
... 

这不是有效的连击。

关于相关主题。

大部分在线代码判断问题都有严格的时间限制。调用`printf（）需要很多时间。

建议，如果可能使用的功能，如：

#include <stdio.h> 


    void fastRead(size_t *a); 
    void fastWrite(size_t a); 

    inline void fastRead(size_t *a) 
    { 
     int c=0; 
     // note: 32 is space character 
     while (c<33) c=getchar_unlocked(); 

     // initialize result value 
     *a=0; 

     // punctuation parens, etc are show stoppers 
     while (c>47 && c<58) 
     { 
      *a = (*a)*10 + (size_t)(c-48); 
      c=getchar_unlocked(); 
     } 
     //printf("%s, value: %lu\n", __func__, *a); 
    } // end function: fastRead 


    inline void fastWrite(size_t a) 
    { 
     char snum[20]; 
     //printf("%s, %lu\n", __func__, a); 

     int i=0; 
     do 
     { 
      // 48 is numeric character 0 
      snum[i++] = (char)((a%10)+(size_t)48); 
      a=a/10; 
     }while(a>0); 

     i=i-1; // correction for overincrement from prior 'while' loop 

     while(i>=0) 
     { 
      putchar_unlocked(snum[i--]); 
     } 
     putchar_unlocked('\n'); 
    } // end function: fastWrite