给定集的功率集

给定一组我想要显示其所有子集（其功率集）。我发现这个代码：给定集的功率集

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

给定集的功率集

回答

相关问题