子序列計算器。我可以讓它更有效率嗎？

Question

子序列的想法在這個崗位被很好的解釋：Generate subsequences

我沒有理解，對這個問題的答案，因爲我是個初學者。

我想知道的是，如果我可以讓我的C程序更高效，同時仍然保持簡單易懂且不需要使用函數？

#include <stdio.h> 
#define NUM 123456 

int main(void) { 

    int i,num=NUM,x,y,mask,digits=0,max=1; 

    while (num != 0) { //calculate digits 
     num /= 10; 
     digits++; 
    } 

    for (i = 1; i <= digits; i++) { //calculate max number of subsequences 
     max *= 2;  
    } 
    max=max-2; 

    printf("Subsequences are:\n"); 
    for (i = 1; i <= max ; i++) { 
     mask = i;  //digit selector 
     x = 1;  //multiplier 
     num = NUM; 
     y=0;   //subsequence value 

     while (num != 0) { 
      if (mask % 2 == 1) { 
       y += num % 10 * x; 
       x *= 10; 
      } 
      num /= 10; 
      mask /= 2; 
     } 
     printf("%d \n" , y); 
    } 

    return 0; 
} 

請注意，當我們將NUM定義爲諸如5111或100的數字時，某些子序列會出現兩次。有沒有簡單的方法來解決這個問題？ 謝謝！

Answer 1

某些子序列出現超過一次的原因的根源是因爲這些數字具有相同數字的重複。

通過將每個子序列保存在數組中並檢查該數組以查看特定的子序列是否已經在數組中，可以消除這種重複。如果已經在數組中，則不要打印。否則，將子序列添加到數組內容並打印

Answer 2

該問題可以分爲兩個任務：（1）查找數字數組的所有子序列和（2）打包並將整數解壓縮爲數字。

我們來考慮數組{a, b, c}的子序列。您可以通過從左到右的方式遍歷數組來生成它們，並遵循兩條路徑：一個包含子序列中的當前元素，另一個包含您不包含的元素。

這導致一個遞歸方法達，我們可以表示成一棵樹：

    {} 
      / \ 
     {}    {a} 
    / \   / \ 
    {}  {b}  {a}  {ab} 
/\ / \ / \ / \ 
    {} {c} {b} {bc} {a} {ac} {ab} {abc} 

當我們離開分支化，我們跳過當前元素，當我們走正確的，我們包括的元素。元素本身就是樹的深度：在第一級，我們將元素a，下一個b和最後一個c。

底行有所有子序列。這包括您不想要的空序列和完整序列。但現在讓我們包括它們。 （底行中的數組通常被稱爲power set，這是一個很好的網頁搜索術語。）

我提到了遞歸，這需要遞歸函數和函數。

所以我們需要以另一種方式解決問題。讓我們轉一下樹。短劃線表示該元素被跳過。右邊的符號使用另一個符號：0意味着元素被跳過，1意味着元素被列入：

- - -  000 
- - c  001 
- b -  010 
- b c  011 
a - -  100 
a - c  101 
a b -  110 
a b c  111 

我希望在右邊的代碼看起來很熟悉，因爲這是你如何指望從000在111二進制文件。這是列舉我們元素的一個好方法。現在我們需要一種方法來確定每個數字中設置了哪些位。

當數字爲奇數時，設置最右邊的位。我們可以通過重複將數字除以2來找出其他位，這在二進制中是向右移位，丟棄最右邊的位。

現在如何從原始數字中提取數字？該數字是十進制數字;它的基數爲10.我們可以使用與查找二進制數中的位相同的方法，因爲位0和位1是二進制數字。

以數字開頭。最後一位數字是將除法後的餘數除以10得到的結果。然後將數字除以10直到它爲零。這段代碼從右到左產生數字。查找位的代碼也是這樣，這意味着我們可以找到是否設置了一位，並在單個循環中打印哪個數字，始終佔據最右邊的位，如果已設置，則打印原始數字的最右邊的數字。

空的和完整的子序列是枚舉中的第一個和最後一個項目。如果你不想要它們，跳過它們。

如果數字有重複數字，則會留下重複子序列的問題。我看不出一個簡單的方法來解決這個問題，除了user3629249建議創建子序列並稍後檢查是否已經打印。

一個簡單的方法來做到這一點是保持一個子序列的數組。該數組有max條目。填充該數組後，對其進行排序並打印，但跳過與前一條目相同的條目。

下面是一個使用數字數組的示例實現，以便每次都不必分解原始數字。它使用排序功能qsort從<stdlib.h>，這需要一個排序功能：

#include <stdlib.h> 
#include <stdio.h> 

#define NUM 412131 

typedef unsigned int uint; 

int uintcmp(const void *pa, const void *pb) 
{ 
    const uint *a = pa; 
    const uint *b = pb; 

    return (*a > *b) - (*a < *b); 
} 

int main(void) 
{ 
    uint digit[20];    // array of digits 
    size_t ndigit = 0;   // length of array 
    uint num = NUM; 
    uint max = 1; 
    size_t i; 

    while (num) { 
     digit[ndigit++] = num % 10; 
     num /= 10; 
     max *= 2; 
    } 

    uint res[max];    // array of subsequences 

    for (i = 0; i < max; i++) { 
     uint mask = i;   // mask for bit detection 
     uint j = ndigit;  // index into digit array 
     uint s = 0; 

     while (j--) { 
      if (mask % 2) s = s*10 + digit[j]; 
      mask /= 2; 
     } 

     res[i] = s; 
    } 

    qsort(res, max, sizeof(*res), uintcmp); 

    for (i = 1; i < max - 1; i++) { 
     if (res[i] != res[i - 1]) printf("%u\n", res[i]); 
    } 

    return 0; 
}