より効率的なリストの組み合わせ

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

バックトラッキングを使用した単純なアルゴリズムを使用することができます。以前の計算の一部を使用してさらに値を得ることを可能にするtechinqueです。

は、ここでは、コードです：

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)です）。再帰的なアルゴリズムに関しては、スタックのメモリを使い果たす可能性もあります。

このコードについて：：ではありません

aa 
bb 
cc 
dd 

：

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

のような誤った出力コンボになります

Answer 2

私はので、ここでそれを配置、コメントよりも多くの部屋を必要と有効なコンボ

このコード：

有効なコンボではありません

aaa 
aab 
aac 
aad 
... 

：

/* 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]); 
     } 
    } 
} 

のような出力コンボになります。

関連する主題について。

多くのオンラインコードジャッジの質問には厳しい制限があります。 `printf（）の呼び出しには多くの時間がかかります。異なるプログラムのカップルを試してみて、より高速である1見えないのはなぜ

#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