Набор питания заданного набора

Question

Учитывая набор, я хочу отобразить все его подмножества (его мощность). Я нашел этот код:

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) есть ли какой-нибудь лучший метод?

Answer 1

Этот 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 ... > 

Answer 2

Этот код ниже остановится быстрее, чем выше алгоритма.

Сложность мудрая, ваша оценка правильная, так как 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"); 
}