如何生成给定集合的幂集? [英] How to generate a power set of a given set?

问题描述

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

I am studying for an interview and I stumbled upon this question online under the "Math" category.

生成给定集合的幂集:

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;

 }

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

Please I do not want an explicit answer. I just want clarifications and hints on how to approach this problem.

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

I checked power set algorithm on google and I still do not understand how to address this problem.

此外，有人可以重申这个问题的要求吗?

Also, could someone reiterate what the question is asking for.

谢谢.

推荐答案

Power set of a set A is the set of all of the subsets of A.

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

Not the most friendly definition in the world, but an example will help :

例如.对于{1, 2}，子集为:{}, {1}, {2}, {1, 2}

Eg. for {1, 2}, the subsets are : {}, {1}, {2}, {1, 2}

因此，功率设置为{{}, {1}, {2}, {1, 2}}

---

要生成幂集，请观察如何创建子集:逐个转到每个元素，然后保留它或忽略它.

---

To generate the power set, observe how you create a subset : you go to each element one by one, and then either retain it or ignore it.

让这个决定用(1/0)表示.

Let this decision be indicated by a bit (1/0).

因此，要生成{1}，您将选择1并放下2(10).

Thus, to generate {1}, you will pick 1 and drop 2 (10).

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

On similar lines, you can write a bit vector for all the subsets :

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

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

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

To reiterate : A subset if formed by including some or all of the elements of the original set. Thus, to create a subset, you go to each element, and then decide whether to keep it or drop it. This means that for each element, you have 2 decisions. Thus, for a set, you can end up with 2^N different decisions, corresponding to 2^N different subsets.

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

See if you can pick it up from here.

这篇关于如何生成给定集合的幂集?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！