查找集合的所有子集

Question

我需要一种算法来查找集合中元素数量为n的集合的所有子集。

S={1,2,3,4...n} 

编辑：我无法理解到目前为止提供的答案。我想逐步了解答案如何找到子集。

例如，

S={1,2,3,4,5} 

你怎么知道{1}和{1,2}是子集？

可能有人帮我在C++中的简单功能找到{1,2,3,4,5}

Answer 1

递归执行此操作非常简单。其基本思想是对于每个元素，子集的集合可以平等地分为那些包含那个元素和那些没有的元素，而这两个集合在其他方面是相等的。

• 对于n = 1，该组的子集是{{}，{1}}
• 对于n> 1时，发现该组1，...，n-1和使两个子集的它的副本。对于其中的一个，将n添加到每个子集。然后采取两个副本的结合。

编辑为了使它晶莹剔透：

• 集合{1}是{{}，{1}}
• 对于{1,2}，取{子集的{}，{1}}，为每个子集添加2以获得{{2}，{1,2}}并且与{{}，{1}}进行合并以得到{{}，{1}，{ 2}，{1,2}}
• 重复，直到你到达ň

Answer 2

子集如果要列举所有可能的子集看看this纸。他们讨论不同的方法，如辞典顺序，灰色编码和银行家的顺序。他们给出了银行家序列的示例实现并讨论了解决方案的不同特征，例如性能。

Answer 3

一个简单的方法を可能是下面的伪代码：

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() 
    } 

} 

嗯，我不完全确定这是对的，但它看起来没问题。

Answer 4

你不必乱搞递归和其他复杂的算法。您可以使用0到2 ^（N-1）之间的所有数字的位模式（小数到二进制）查找所有子集。这里N是该集合中的基数或项数。这个技术在这里用一个实现和演示来解释。

http://codeding.com/?article=12

Answer 5

这里是Scala中的一个解决方案：

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) 
} 

Answer 6

来不及回答，但迭代的方法听起来这里简单：一组n个元素）

1，得到值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，形成一个子集，其中的元素与二进制表示中的索引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中找到的所有子集的联合。
Eg. Simple union of above sets!

Answer 7

这是一些伪代码。通过随时随地存储每个呼叫的值，并在递归呼叫检查之前（如果呼叫值已存在），可以剪切相同的递归调用。

以下算法将具有排除空集的所有子集。

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; 
    } 
} 

Answer 8

万一别人来通过，并仍然不知道，这里是通过在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与所有可能的子集，这意味着可能会有重复。如果你不想要这个，我会建议实际使用set而不是vector（我用它来避免代码中的迭代器）。

Answer 9

这里是我写的，前一段时间

// 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())); 
} 

Answer 10

这里工作的代码，我已经详细解释它。 如果你喜欢博客帖子，请点赞。

http://cod3rutopia.blogspot.in/

，如果你不能找到我的博客在这里任何方式的解释。

它是一个本质上递归的问题。

本质上为元素存在于一个子集有2个选项：

1）是存在于所述集合

2）它是在该组不存在。

这就是为什么一组n个数字的具有2^N的子集的原因。（每个元件2的选项）

这里是伪代码（C++）来打印所有子集，接着一个例子，说明如何代码起作用。 1）A []是你想要找出其子集的数组的数组。 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) 
    } 
    } 

Answer 11

这里是我的递归解决方案。

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; 
    } 


} 

Answer 12

底向上与O（N）空间溶液

#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); 
} 

Answer 13

这里是在python一个简单的递归算法寻找一组的所有子集：

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 [] [] 
[] 

观看斯坦福以下视频这个算法的一个很好的解释：

https://www.youtube.com/watch?v=NdF1QDTRkck&feature=PlayList&p=FE6E58F856038C69&index=9 

Answer 14

简单bitmasking可以做的伎俩如前所述....由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; 
} 

Answer 15

这是一个实现Michael的解决方案的任何类型的元素在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 

Answer 16

对于那些使用std :: vector和std ::对于迈克尔博格瓦特的算法设置谁想要一个简单的实现：

// 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; 
} 

Answer 17

这个问题老了。但是OP的问题有一个简单而优雅的递归解决方案。

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