我需要一種算法來查找集合中所有元素的集合的子集n。S={1,2,3,4...n}編輯：我目前無法理解所提供的答案。我想逐步說明答案如何找到子集。例如，S={1,2,3,4,5}你怎么知道{1}和{1,2}是子集？有人可以幫我用C ++中的一個簡單函數來查找{1,2,3,4,5}的子集
3 回答
搖曳的薔薇
TA貢獻1793條經驗 獲得超6個贊
遞歸執行此操作非常簡單?；舅枷胧?，對于每個元素，可以將子集劃分為包含該元素的子集和不包含子元素的子集，否則這兩組子集是相等的。
對于n = 1，子集為{{}，{1}}
對于n> 1，找到1，...，n-1的子集，并制作兩個副本。對于其中之一，將n添加到每個子集。然后將兩個副本合并。
編輯使其清晰可見：
{1}的子集為{{}，{1}}
對于{1，2}，取{{}，{1}}，向每個子集加2以得到{{2}，{1，2}}，并與{{}，{1}}取并{{}，{1}，{2}，{1、2}}
重復直到達到n
胡說叔叔
TA貢獻1804條經驗 獲得超8個贊
回答為時已晚，但是在這里聽起來很容易采用迭代方法：
1）對于一組n元素，獲取的值2^n。將有2 ^ n個子集。（2 ^ n，因為每個元素可以是present（1）或不存在（0）。因此對于n個元素，將有2 ^ n個子集。）例如：
for 3 elements, say {a,b,c}, there will be 2^3=8 subsets
2）獲得的二進制表示形式2^n。例如：
8 in binary is 1000
3）從0轉到(2^n - 1)。在每次迭代中，對于二進制表示形式中的每個1，請形成一個子集，其子元素對應于二進制表示形式中該1的索引。例如：
For the elements {a, b, c}
000 will give {}
001 will give {c}
010 will give
011 will give {b, c}
100 will give {a}
101 will give {a, c}
110 will give {a, b}
111 will give {a, b, c}
4）對在步驟3中找到的所有子集進行并集。返回。例如：
Simple union of above sets!
aluckdog
TA貢獻1847條經驗 獲得超7個贊
萬一其他人來了并且仍然想知道，這是一個使用C ++中邁克爾的解釋的函數
vector< vector<int> > getAllSubsets(vector<int> set)
{
vector< vector<int> > subset;
vector<int> empty;
subset.push_back( empty );
for (int i = 0; i < set.size(); i++)
{
vector< vector<int> > subsetTemp = subset;
for (int j = 0; j < subsetTemp.size(); j++)
subsetTemp[j].push_back( set[i] );
for (int j = 0; j < subsetTemp.size(); j++)
subset.push_back( subsetTemp[j] );
}
return subset;
}
但是要考慮到，這將返回一組大小為2 ^ N的集合，其中包含所有可能的子集，這意味著可能存在重復項。如果您不希望這樣做，我建議您實際使用a set而不是a vector（我曾經使用它來避免代碼中的迭代器）。
- 3 回答
- 0 關注
- 834 瀏覽
添加回答
舉報
0/150
提交
取消