如何生成给定集的幂集？

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

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.

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

Answer 2

功率集只是给定集的所有子集的集合.它包括所有子集(空集).众所周知,这个集合中有2个^N元素,其中N是原始集合中元素的数量.

要构建电源组,可以使用以下内容:

• 创建一个循环,迭代从0到2 ^N -1的所有整数
• 继续进行每个整数的二进制表示
• 每个二进制表示是一组N位(对于较小的数字,添加前导零).如果特定集合成员包括在当前子集中,则每个位对应.

例如,3个数字:a,b,c

number binary  subset
0      000      {}
1      001      {c}
2      010      {b}
3      011      {b,c}
4      100      {a}
5      101      {a,c}
6      110      {a,b}
7      111      {a,b,c}

Answer 3

创建一个以下的权力集:{"A", "B", "C"}.

伪代码:

val set = {"A", "B", "C"}

val sets = {}

for item in set:
  for set in sets:
    sets.add(set + item)
  sets.add({item})
sets.add({})

算法说明:

1)初始化sets为空集:{}.

2)迭代每个项目 {"A", "B", "C"}

3)迭代set你的每一个sets.

3.1)创建一个新的集合,它是一个副本set.

3.2)附加item到new set.

3.3)附加new set到sets.

4)添加item到您的sets.

4)迭代完成.将空集添加到您的resultSets.

演练:

让我们看看sets每次迭代后的内容:

迭代1,item ="A":

sets = {{"A"}}

迭代2,项目="B":

sets = {{"A"}, {"A", "B"}, {"B"}}

迭代3,item ="C":

sets = {{"A"}, {"A", "B"}, {"B"}, {"A", "C"}, {"A", "B", "C"}, {"B", "C"}, {"C"}}

迭代完成,添加空集:

sets = {{"A"}, {"A", "B"}, {"B"}, {"A", "C"}, {"A", "B", "C"}, {"B", "C"}, {"C"}, {}}

集合的大小为2 ^ | set | = 2 ^ 3 = 8这是正确的.

Java中的示例实现:

public static <T> List<List<T>> powerSet(List<T> input) {
  List<List<T>> sets = new ArrayList<>();
  for (T element : input) {
    for (ListIterator<List<T>> setsIterator = sets.listIterator(); setsIterator.hasNext(); ) {
      List<T> newSet = new ArrayList<>(setsIterator.next());
      newSet.add(element);
      setsIterator.add(newSet);
    }
    sets.add(new ArrayList<>(Arrays.asList(element)));
  }
  sets.add(new ArrayList<>());
  return sets;
}

输入: [A, B, C]

输出: [[A], [A, C], [A, B], [A, B, C], [B], [B, C], [C], []]