주어진 세트의 힘 세트

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