转载

集合习题之列出有限集合所有子集

1、题目（《离散数学及其应用》第6版P75 20 题）

给出可以列出有限集合所有子集的步骤。

2、解题思路

假设有集合A = {a1, a2 … an}，列出其所有子集。

先列出含有1个元素的所有子集：{a1},{a2} … {an}
然后列出含有2个元素的所有子集：{a1,a2},{a1,a3}…{an-1,an}
同上所示，一直列到含有n个元素的所有子集

可以看出，问题就简化为求在 A 集合中，求含有固定 x 个元素的所有子集（注意，子集中每个ai只能包含一次）。

这实际上类似这么个问题，袋子中有编号为1到10的10个球，每次取一个球，取出后不放回袋子，取3次，问取出的3个球的编号可能的所有组合。

方法：

取第1个球时，有1～10种取法
取第2个球时，如果知道第1个球取的编号是a，则第2个球有除a以外的9种取法，但要注意{1,2}和{2,1}是同一个子集，如何保证不取已经取过了的同一组编号的球？

我们可以观察到如果让{1,2}2个球按编号大小排列只有一种排列方式即{1,2},所以只要保证第2个球的编号比第一个球的编号大，即可保证不会取到{2,1}

所以，我们可以在取第2个球时，从 (a+1) 开始取，即可保证不会取到重复的排列方式

同时，我们取第3个球时，一样需要知道第1、2个球的编号，这实际上就是一个递归问题了，假设已知取到第1个球为a，第2个球为b，则第三个球的取法为 {(b+1) …10)}

3、算法

 //功能：从m个元素（元素不重复）中取出n个元素（n <= m）的所有取法 //参数：vectorHead = 前nBit_x - 1个元素已取了的头部vector //参数：nHeadBit = 当前处理的元素在vectorSet中的位置 //参数：nBit_x = 当前要处理的子集的元素位置 //参数：nChildSetSize= 要取的n个元素的子集的大小 //参数：vectorSet = m个元素的总集 //参数：vectorChildSetBuffer = 存放子集的buffer //返回：当前操作的步数 int    GetChildSetByDec(std::vector<int>& vectorHead, int nHeadBit, int nBit_x, int nChildSetSize, std::vector<int>& vectorSet, std::vector<std::vector<int>>& vectorChildSetBuffer) {     int    nRet  = 0;      for (int i = nHeadBit; i < vectorSet.size(); i++)     {         nRet++;          std::vector<int>    vectorNewHead = vectorHead;         vectorNewHead.push_back(vectorSet[i]);          if (nBit_x == nChildSetSize - 1)         {             //如果已经处理到最后一位了，则添加到buffer中             vectorChildSetBuffer.push_back(vectorNewHead);         }         else         {             //如果还没处理到最后一位，则递归             GetChildSetByDec(vectorNewHead, i + 1, nBit_x + 1, nChildSetSize, vectorSet, vectorChildSetBuffer);         }     }      return    nRet; }  //功能：从m个元素（元素不重复）中取出n个元素（n <= m）的所有取法 //参数：nChildSize = 要取的n个元素的子集的大小 //参数：vectorBuffer = 存放所有数组的buffer //参数：vectorSet = m个元素的总集 //返回：无 void    GetChildSet(std::vector<std::vector<int>>& vectorChildSetBuffer, std::vector<int>& vectorSet) {     //依次列出从1个元素到n个元素的集合     for (int i = 1; i <= vectorSet.size(); i++)     {         std::vector<int> vectorHead;          GetChildSetByDec(vectorHead, 0, 0, i, vectorSet, vectorChildSetBuffer);     } }

说明：

这里用的 vectorChildAggregateBuffer 来存放返回的子集，vectorChildAggregateBuffer 是一个STL容器中向量的向量，如果没有用过STL，可以理解为数组的指针（Array[][]）,这里用Vector是为了存储操作方便。
GetChildAggregateByDec() 函数即用递归实现上面例子中10个球中取3个球的所有取法遍历。
GetChildAggregateByDec() 中运用了将n个元素映射为 Array[n] 数组一一对应的思想