find一个集合的所有子集
我需要一个algorithm来查找集合中元素个数为n的集合的所有子集。
S={1,2,3,4...n}
编辑：我无法理解迄今为止提供的答案。 我希望有一些循序渐进的例子来说明答案如何find子集。
例如，
S={1,2,3,4,5}
你怎么知道{1}和{1,2}是子集？
有人可以用c ++中的一个简单函数来帮我find{1,2,3,4,5}
recursion地做这件事非常简单。 其基本思想是，对于每个元素，子集的集合可以平等地分为那些包含那个元素和那些没有的元素，而那两个集合是相等的。
- 对于n = 1，子集的集合是{{}，{1}}
- 对于n> 1，find1，…，n-1的子集的集合，并创build它的两个副本。 对于其中的一个，将n添加到每个子集。 然后把这两个副本结合起来。
编辑为了让它透明：
- {1}的子集的集合是{{}，{1}}
- 对于{1,2}，取{{}，{1}}，对每个子集加2得到{{2}，{1,2}}并与{{}，{1}}进行合并，得到{{}，{1}，{2}，{1，2}}
- 重复，直到你到达n
答案太迟，但在这里听起来很简单：
1）对于一组n个元素，得到2 ^ n的值。 将会有2 ^ n个子集。 （2 ^ n，因为每个元素可以存在（1）或不存在（0），所以对于n个元素将有2 ^ n个子集）。
Eg. for 3 elements, say {a,b,c}, there will be 2^3=8 subsets
2）获得2 ^ n的二进制表示。
Eg. 8 in binary is 1000
3）从0到（2 ^ n – 1）。 在每次迭代中，对于二进制表示中的每个1，形成一个子集，其中的元素对应于二进制表示中的索引。
例如：
For the elements {a, b, c} 000 will give {} 001 will give {c} 010 will give {b} 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中find所有子集的联合。
Eg. Simple union of above sets!
如果有其他人来了，仍然想知道，这是一个使用迈克尔在C ++中的解释function
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的所有可能的子集，这意味着可能会有重复。 如果你不想要这个，我会build议实际使用一个set而不是一个vector （我用它来避免代码中的迭代器）。
如果你想列举所有可能的子集，请看本文。 他们讨论不同的方法，如词典顺序，灰色编码和银行家的顺序。 他们给出了一个银行家序列的例子实现，并讨论了解决scheme的不同特点，例如性能。
这里我详细解释一下。 如果你喜欢这个博客，请注意。
http://cod3rutopia.blogspot.in/
任何方式，如果你不能在这里find我的博客是解释。
它是一个recursion的问题。
本质上，一个元素出现在一个子集中有两个选项：
1）存在于集合中
2）在集合中不存在。
这就是为什么一组n个数字有2 ^ n个子集（每个元素有两个选项）
这里是打印所有子集的伪代码（C ++），后面跟着一个解释代码如何工作的例子。 1）A []是你想要find的子集的数组。 2）bool a []是布尔数组，其中a [i]表示数组A [i]是否出现在集合中。
print(int A[],int low,int high) { if(low>high) { for(all entries i in bool a[] which are true) print(A[i]) } else {set a[low] to true //include the element in the subset print(A,low+1,high) set a[low] to false//not including the element in the subset print(A,low+1,high) } }
你不必乱搞recursion和其他复杂的algorithm。 您可以使用0到2 ^（N-1）之间的所有数字的位模式（十进制到二进制）来查找所有子集。 这里N是该集合中的基数或项数。 这个技巧在这里用一个实现和演示来解释。
这里是一个简单的Pythonrecursionalgorithm，用于查找集合的所有子集：
def find_subsets(so_far, rest): print 'parameters', so_far, rest if not rest: print so_far else: find_subsets(so_far + [rest[0]], rest[1:]) find_subsets(so_far, rest[1:]) find_subsets([], [1,2,3])
输出将如下所示：$ python subsets.py
parameters [] [1, 2, 3] parameters [1] [2, 3] parameters [1, 2] [3] parameters [1, 2, 3] [] [1, 2, 3] parameters [1, 2] [] [1, 2] parameters [1] [3] parameters [1, 3] [] [1, 3] parameters [1] [] [1] parameters [] [2, 3] parameters [2] [3] parameters [2, 3] [] [2, 3] parameters [2] [] [2] parameters [] [3] parameters [3] [] [3] parameters [] [] []
观看下面这个来自斯坦福大学的video，对这个algorithm做个很好的解释：
https://www.youtube.com/watch?v=NdF1QDTRkck&feature=PlayList&p=FE6E58F856038C69&index=9
这是Scala中的一个解决scheme：
def subsets[T](s : Set[T]) : Set[Set[T]] = if (s.size == 0) Set(Set()) else { val tailSubsets = subsets(s.tail); tailSubsets ++ tailSubsets.map(_ + s.head) }
这是一些伪代码。 您可以通过随时随地存储每个呼叫的值并在recursion呼叫检查之前（如果呼叫值已经存在）来削减相同的recursion调用。
以下algorithm将具有排除空集的所有子集。
list * subsets(string s, list * v){ if(s.length() == 1){ list.add(s); return v; } else { list * temp = subsets(s[1 to length-1], v); int length = temp->size(); for(int i=0;i<length;i++){ temp.add(s[0]+temp[i]); } list.add(s[0]); return temp; } }
这是我前一段时间写的一个工作代码
// Return all subsets of a given set #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<string> #include<sstream> #include<cstring> #include<climits> #include<cmath> #include<iterator> #include<set> #include<map> #include<stack> #include<queue> using namespace std; typedef vector<int> vi; typedef vector<long long> vll; typedef vector< vector<int> > vvi; typedef vector<string> vs; vvi get_subsets(vi v, int size) { if(size==0) return vvi(1); vvi subsets = get_subsets(v,size-1); vvi more_subsets(subsets); for(typeof(more_subsets.begin()) it = more_subsets.begin(); it !=more_subsets.end(); it++) { (*it).push_back(v[size-1]); } subsets.insert(subsets.end(), (more_subsets).begin(), (more_subsets).end()); return subsets; } int main() { int ar[] = {1,2,3}; vi v(ar , ar+int(sizeof(ar)/sizeof(ar[0]))); vvi subsets = get_subsets(v,int((v).size())); for(typeof(subsets.begin()) it = subsets.begin(); it !=subsets.end(); it++) { printf("{ "); for(typeof((*it).begin()) it2 = (*it).begin(); it2 !=(*it).end(); it2++) { printf("%d,",*it2 ); } printf(" }\n"); } printf("Total subsets = %d\n",int((subsets).size()) ); }
这里是迈克尔的解决scheme的任何types的元素在std :: vector的实现。
#include <iostream> #include <vector> using std::vector; using std::cout; using std::endl; // Find all subsets template<typename element> vector< vector<element> > subsets(const vector<element>& set) { // Output vector< vector<element> > ss; // If empty set, return set containing empty set if (set.empty()) { ss.push_back(set); return ss; } // If only one element, return itself and empty set if (set.size() == 1) { vector<element> empty; ss.push_back(empty); ss.push_back(set); return ss; } // Otherwise, get all but last element vector<element> allbutlast; for (unsigned int i=0;i<(set.size()-1);i++) { allbutlast.push_back( set[i] ); } // Get subsets of set formed by excluding the last element of the input set vector< vector<element> > ssallbutlast = subsets(allbutlast); // First add these sets to the output for (unsigned int i=0;i<ssallbutlast.size();i++) { ss.push_back(ssallbutlast[i]); } // Now add to each set in ssallbutlast the last element of the input for (unsigned int i=0;i<ssallbutlast.size();i++) { ssallbutlast[i].push_back( set[set.size()-1] ); } // Add these new sets to the output for (unsigned int i=0;i<ssallbutlast.size();i++) { ss.push_back(ssallbutlast[i]); } return ss; } // Test int main() { vector<char> a; a.push_back('a'); a.push_back('b'); a.push_back('c'); vector< vector<char> > sa = subsets(a); for (unsigned int i=0;i<sa.size();i++) { for (unsigned int j=0;j<sa[i].size();j++) { cout << sa[i][j]; } cout << endl; } return 0; }
输出：
(empty line) a b ab c ac bc abc
一个简单的方法是下面的伪代码：
Set getSubsets(Set theSet) { SetOfSets resultSet = theSet, tempSet; for (int iteration=1; iteration < theSet.length(); iteration++) foreach element in resultSet { foreach other in resultSet if (element != other && !isSubset(element, other) && other.length() >= iteration) tempSet.append(union(element, other)); } union(tempSet, resultSet) tempSet.clear() } }
那么我并不确定这是正确的，但它看起来不错。
这是我的recursion解决scheme。
vector<vector<int> > getSubsets(vector<int> a){ //base case //if there is just one item then its subsets are that item and empty item //for example all subsets of {1} are {1}, {} if(a.size() == 1){ vector<vector<int> > temp; temp.push_back(a); vector<int> b; temp.push_back(b); return temp; } else { //here is what i am doing // getSubsets({1, 2, 3}) //without = getSubsets({1, 2}) //without = {1}, {2}, {}, {1, 2} //with = {1, 3}, {2, 3}, {3}, {1, 2, 3} //total = {{1}, {2}, {}, {1, 2}, {1, 3}, {2, 3}, {3}, {1, 2, 3}} //return total int last = a[a.size() - 1]; a.pop_back(); vector<vector<int> > without = getSubsets(a); vector<vector<int> > with = without; for(int i=0;i<without.size();i++){ with[i].push_back(last); } vector<vector<int> > total; for(int j=0;j<without.size();j++){ total.push_back(without[j]); } for(int k=0;k<with.size();k++){ total.push_back(with[k]); } return total; } }
自下而上的O（N）空间解决scheme
#include <stdio.h> void print_all_subset(int *A, int len, int *B, int len2, int index) { if (index >= len) { for (int i = 0; i < len2; ++i) { printf("%d ", B[i]); } printf("\n"); return; } print_all_subset(A, len, B, len2, index+1); B[len2] = A[index]; print_all_subset(A, len, B, len2+1, index+1); } int main() { int A[] = {1, 2, 3, 4, 5, 6, 7}; int B[7] = {0}; print_all_subset(A, 7, B, 0, 0); }
一个简单的掩码可以做到这一点，如前所述…. rgamber
#include<iostream> #include<cstdio> #define pf printf #define sf scanf using namespace std; void solve(){ int t; char arr[99]; cin >> t; int n = t; while( t-- ) { for(int l=0; l<n; l++) cin >> arr[l]; for(int i=0; i<(1<<n); i++) { for(int j=0; j<n; j++) if(i & (1 << j)) pf("%c", arr[j]); pf("\n"); } } } int main() { solve(); return 0; }
对于那些想要使用std :: vector和std :: set来实现Michael Borgwardtalgorithm的简单实现的人来说：
// Returns the subsets of given set vector<set<int> > subsets(set<int> s) { vector<set<int> > s1, s2; set<int> empty; s1.push_back(empty); // insert empty set // iterate over each element in the given set for(set<int>::iterator it=s.begin(); it!=s.end(); ++it) { s2.clear(); // clear all sets in s2 // create subsets with element (*it) for(vector<set<int> >::iterator s1iter=s1.begin(); s1iter!=s1.end(); ++s1iter) { set<int> temp = *s1iter; temp.insert(temp.end(), *it); s2.push_back(temp); } // update s1 with new sets including current *it element s1.insert(s1.end(), s2.begin(), s2.end()); } // return return s1; }
这个问题很老。 但是OP的问题有一个简单优雅的recursion解决scheme。
using namespace std; void recsub(string sofar, string rest){ if(rest=="") cout<<sofar<<endl; else{ recsub(sofar+rest[0], rest.substr(1)); //including first letter recsub(sofar, rest.substr(1)); //recursion without including first letter. } } void listsub(string str){ recsub("",str); } int main(){ listsub("abc"); return 0; } //output abc ab ac a bc b c //end: there's a blank output too representing empty subset
