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

  • Z时代
  • 2024-01-10
  • 分类：问答

我正在研究面试，并且在网上“数学”类别下偶然发现了这个问题。

生成给定集合的幂集：

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

请不要明确的答案。我只想澄清和提示如何解决此问题。

我在Google上检查了功率设置算法，但仍然不明白如何解决此问题。

另外，有人可以重申问题的要求吗？

谢谢。

回答：

Power set of a set A is the set of all of the subsets of 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。

看看是否可以从这里拿起它。

以上是 如何生成给定集合的幂集？ 的全部内容， 来源链接： utcz.com/qa/410365.html

回到顶部