1、題目（《離散數(shù)學(xué)及其應(yīng)用》第6版P75 20 題）

??? 給出可以列出有限集合所有子集的步驟。

2、? 解題思路

假設(shè)有集合A = {a1, a2 … an}，列出其所有子集。

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

可以看出，問題就簡化為求在 A 集合中，求含有固定 x 個(gè)元素的所有子集（注意，子集中每個(gè)ai只能包含一次）。

這實(shí)際上類似這么個(gè)問題，袋子中有編號為1到10的10個(gè)球，每次取一個(gè)球，取出后不放回袋子，取3次，問取出的3個(gè)球的編號可能的所有組合。

方法：

• 取第1個(gè)球時(shí)，有1～10種取法
• 取第2個(gè)球時(shí)，如果知道第1個(gè)球取的編號是a，則第2個(gè)球有除a以外的9種取法，但要注意{1,2}和{2,1}是同一個(gè)子集，如何保證不取已經(jīng)取過了的同一組編號的球？

我們可以觀察到如果讓{1,2}2個(gè)球按編號大小排列只有一種排列方式即{1,2},所以只要保證第2個(gè)球的編號比第一個(gè)球的編號大，即可保證不會取到{2,1}

所以，我們可以在取第2個(gè)球時(shí)，從 (a+1) 開始取，即可保證不會取到重復(fù)的排列方式

同時(shí)，我們?nèi)〉?個(gè)球時(shí)，一樣需要知道第1、2個(gè)球的編號，這實(shí)際上就是一個(gè)遞歸問題了，假設(shè)已知取到第1個(gè)球?yàn)閍，第2個(gè)球?yàn)閎，則第三個(gè)球的取法為 {(b+1) …10)}

3、算法

//功能：從m個(gè)元素（元素不重復(fù)）中取出n個(gè)元素（n <= m）的所有取法 //參數(shù)：vectorHead = 前nBit_x - 1個(gè)元素已取了的頭部vector //參數(shù)：nHeadBit = 當(dāng)前處理的元素在vectorSet中的位置 //參數(shù)：nBit_x = 當(dāng)前要處理的子集的元素位置 //參數(shù)：nChildSetSize= 要取的n個(gè)元素的子集的大小 //參數(shù)：vectorSet = m個(gè)元素的總集 //參數(shù)：vectorChildSetBuffer = 存放子集的buffer //返回：當(dāng)前操作的步數(shù) 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){//如果已經(jīng)處理到最后一位了，則添加到buffer中 vectorChildSetBuffer.push_back(vectorNewHead);}else{//如果還沒處理到最后一位，則遞歸GetChildSetByDec(vectorNewHead, i + 1, nBit_x + 1, nChildSetSize, vectorSet, vectorChildSetBuffer);}}return nRet; }//功能：從m個(gè)元素（元素不重復(fù)）中取出n個(gè)元素（n <= m）的所有取法 //參數(shù)：nChildSize = 要取的n個(gè)元素的子集的大小 //參數(shù)：vectorBuffer = 存放所有數(shù)組的buffer //參數(shù)：vectorSet = m個(gè)元素的總集 //返回：無 void GetChildSet(std::vector<std::vector<int>>& vectorChildSetBuffer, std::vector<int>& vectorSet) {//依次列出從1個(gè)元素到n個(gè)元素的集合for (int i = 1; i <= vectorSet.size(); i++){std::vector<int> vectorHead;GetChildSetByDec(vectorHead, 0, 0, i, vectorSet, vectorChildSetBuffer);} }

?

說明：

• 這里用的 vectorChildAggregateBuffer 來存放返回的子集，vectorChildAggregateBuffer 是一個(gè)STL容器中向量的向量，如果沒有用過STL，可以理解為數(shù)組的指針（Array[][]）,這里用Vector是為了存儲操作方便。
• GetChildAggregateByDec() 函數(shù)即用遞歸實(shí)現(xiàn)上面例子中10個(gè)球中取3個(gè)球的所有取法遍歷。
• GetChildAggregateByDec() 中運(yùn)用了將n個(gè)元素映射為 Array[n] 數(shù)組一一對應(yīng)的思想

程序運(yùn)行結(jié)果：

?

如有其他思路解題，歡迎大家跟帖討論

轉(zhuǎn)載于:https://www.cnblogs.com/organic/p/5015246.html

總結(jié)

以上是生活随笔為你收集整理的集合习题之列出有限集合所有子集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。