集合習題之列出有限集合所有子集

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] 數組一一對應的思想

程序運行結果：

?

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