algorithm - 如何生成给定集合的幂集？

Question

我正在为面试而学习，我在网上的“数学”类别下偶然发现了这个问题。

生成给定集合的幂集:

int A[] = {1,2,3,4,5};  
int N = 5; 
int Total = 1 << N;
for ( int i = 0; i < Total; i++ ) { 
 for ( int j = 0; j < N; j++) {
  if ( (i >> j) & 1 ) 
      cout << A[j]; 
   } 
 cout <<endl;

 }

拜托，我不想要一个明确的答案。我只想得到有关如何解决此问题的说明和提示。

我在谷歌上查了幂集算法，但我仍然不明白如何解决这个问题。

此外，有人可以重申问题的要求吗。

谢谢。

Answer 1

集合 A 的幂集是 A 的所有子集的集合。

这不是世界上最友好的定义，但一个例子会有所帮助:

例如。对于 {1, 2}，子集是:{}, {1}, {2}, {1, 2}

因此，幂集是{{}, {1}, {2}, {1, 2}}

---

要生成幂集，请观察如何创建子集:您一个一个地访问每个元素，然后保留它或忽略它。

让这个决定由一位 (1/0) 表示。

因此，要生成 {1}，您将选择 1 并删除 2 (10)。

在类似的行中，您可以为所有子集编写一个位向量:

• {} -> 00
  {1} -> 10
  {2} -> 01
  {1,2} -> 11

重申:如果通过包含原始集合的部分或全部元素而形成子集。因此，要创建一个子集，您需要找到每个元素，然后决定是保留还是删除它。这意味着对于每个元素，您有 2 个决定。因此，对于一个集合，您最终可以得到 2^N 个不同的决策，对应于 2^N 个不同的子集。

看看你能不能从这里拿走它。