給定集的功率集

給定一組我想要顯示其所有子集（其功率集）。我發現這個代碼：給定集的功率集

void printPowerSet(char *set, int set_size) 
{ 
    /*set_size of power set of a set with set_size 
     n is (2**n -1)*/ 
    unsigned int pow_set_size = pow(2, set_size); 
    int counter, j; 

    /*Run from counter 000..0 to 111..1*/ 
    for(counter = 0; counter < pow_set_size; counter++) 
    { 
     for(j = 0; j < set_size; j++) 
     { 

      if(counter & (1<<j)) 
      printf("%c", set[j]); 
     } 
     printf("\n"); 
    } 
}

我不明白爲什麼這部分是用來

if(counter & (1<<j))

什麼是它的意義？

該算法的時間複雜度爲O(n2^n)有沒有更好的方法？

來源

2014-09-22 starter

這轉換爲：如果'counter'，按位有位nbr。 'j'設置爲1，則... – 2014-09-22 12:15:35

輸出的大小爲O（n * 2^n），所以不能有漸近更快的方法。 – interjay 2014-09-22 12:21:27

這if檢查是否設置位j。例如，當j == 0我們正在尋找（我使用簡單的8位）：

XXXXXXX? & 00000001

其中X是「不關心」，?就是我們要檢查。然後，當j == 1

XXXXXX?X & 00000010

換句話說，它是檢查是否一個位被設置或取消，這決定了相應的一組元素是否包含在當前組或不是一個方便的方法。至於複雜性，由於在功率集中有2^n集，所以很難想象一個更快的算法來生成它們全部。

產生功率集的原因是二進制計數器會耗盡所有n位值的組合，請參閱以下示例。

例

組：{1，2，3}

counter 1<<j intermediate result final 
    000 001 N/A 
    000 010 N/A 
    000 100 N/A 
             {} 
    001 001 3 
    001 010 N/A 
    001 100 N/A 
             {3} 
    < ... skip a few iterations ... > 
    101 001 3 
    101 010 N/A 
    101 100 1 
             {1,3} 
    < ... etc ... >

來源

2014-09-22 12:21:15 FatalError

爲什麼要使用左移位器<< – starter 2014-09-22 12:44:58

'1'是除最低位以外的所有位爲0的值。左移'n'位會產生一個只設置了'n'位的值 - 它允許根據'j'計數器的值計算適當的位掩碼。 – FatalError 2014-09-22 12:47:45

不是很清楚!!!! – 2014-09-22 12:49:26

此代碼下面將停止除上述算法更快。

複雜性明智，您的評估是正確的，因爲O（N * 2^N）是輸出的大小。

unsigned c; 
for (counter = 0; counter < pow_set_size; counter++) { 

    for (c = counter; c != 0;) { 
     if(c & 1) { 
      printf("%c", set[j]); 
     } 
     c = c >> 1; // drop lsb 
    } 
    printf("\n"); 
}

來源

2014-09-22 13:01:18 egur

給定集的功率集

回答

相關問題