Thread: Find all possible subset of a given set

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    4

    Find all possible subset of a given set

    Code:
    If we have set  A that is represented as A =  {1,2,3,4}. How can  we generate the all possible of set B  such that  B is subset of A and A is not equal to B by  writing C or C++ programming.
    
    Ex.     If   A =  {1,2,3,4} then,  we will have the all possible of set B  under above condition as following:
    
    B1={1}, B2={2}, B3={3}, B4={4},
    B5={1,2}, B6={1,3}, B7={1,4}, 
    B8={2,3}, B9={2,4}, B10={3,4}, 
    B11={1,2,3}, B12={1,2,4}, B13={1,3,4}, B14={2,3,4}
    
    Note:  we think that two sets  that have the same member are the same set althrough they have different sequence. For example set {1,2,3} or {3,1,2}   are the same set.
    Last edited by Downnin; 04-24-2005 at 02:46 PM.

  2. #2
    Registered User
    Join Date
    Mar 2005
    Posts
    38
    Ah, also called "kSubsets", right? I have an implementation ready...

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    You forgot about
    B0={} The empty set.

    Compare the sets you generate from A={1,2,3} with the sets you generate with A={1,2,3,4}

    Once you see the pattern of how the sets are generated from adding one element to the set, you should be able to work out a nice recursive approach which finishes when you get to an easy case of all the sub-sets of A={1}.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Mar 2005
    Posts
    38
    With my comment on kSubsets, I meant the subsets with a fixed number of elements: k. There are exactly binomial(n,k) of them, with n the size of the input set.

    You can enumerate these kSubsets easily by forming index vectors. Example:
    Code:
    input list = {-1,2,4,6}, k = 2
    index vectors: {0,1},{0,2},{0,3},{1,2},{1,3},{2,3}
    corresponding subsets: {-1,2},{-1,4},{-1,6},{2,4},{2,6},{4,6}
    Recursion might be an elegant way to program it, but I'd avoid it.

  5. #5
    Registered User
    Join Date
    Apr 2005
    Posts
    22
    Off the top of my head, here is a possible recursive algorithm for doing this. However, it is very inefficient and i think it stores differrent permutations of a same subset (e.g. it'll see {1, 2, 3} and {2, 1, 3} as differrent subsets)

    Code:
    void generateSubsets(vector<int>& set, set<vector<int> >&subsets) {
      for(vector<int>::iterator vi = set.begin(); vi != set.end(); ++vi) {
        vector<int> subset = set;
        subset.erase(*vi);
        subsets.insert(subset);
        if(subset.size() > 1) generateSubsets(subset, subsets);
      }
    }
    P.S. if set is declared as a std::set<int> rather than std::vector<int> i think it'll work correctly. However, its still very inefficient and i think there is a much better dynamic programming solution.
    Togra, it would be interesting to see your kSubsets solution.

  6. #6
    Registered User
    Join Date
    Mar 2005
    Posts
    38
    It's quite ugly, but you asked for it .

    Code:
    template <typename T>
    std::vector<T> range(T curr, T const &up)
    {
      std::vector<T> result;
      for (; curr <= up; ++curr)
        result.push_back(curr);
      return result;
    }
    
    template <typename T>
    std::vector< std::vector<T> > kSubsets(std::vector<T> vec, unsigned k)
    {
      std::vector< std::vector<T> > result;
      if (!k)
        return result;
      int n = vec.size();
      std::vector<int> idx_vec = range<int>(0, k - 1);
      while (true)
      {
        int pos;
        result.push_back(idx_vec);
        for (pos = 0; pos < result.back().size(); ++pos)
          result.back()[pos] = vec[result.back()[pos]];
        // next kSubset
        pos = k - 1;
        ++idx_vec[pos];
        while (idx_vec[pos] >= n + pos - k + 1)
        {
          if (--pos < 0)
            return result;
          ++idx_vec[pos];
          for (int i = pos + 1; i < k; ++i)
            idx_vec[i] = idx_vec[pos] + i - pos;
        }
      }
      // unreachable
      return result;
    }

  7. #7
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    Recursion is probably the easiest way to solve this. For the base case, you have the empty set. The number of subsets of the empty set is one, the empty set. To progress to more general sets, look at an example. If we'll trying to find the subsets of {3, 4, 5, 2, 1}, then they may be found by adding the subsets of {4, 5, 2, 1} to the subsets containing the first element. The former, the subsets of {4, 5, 2, 1}, is a smaller set than {3, 4, 5, 2, 1} and can thus be solved recursively. The latter, however, in't so easy. If you think about it, though, the subsets of {3, 4, 5, 2, 1} such that they all contain 3 are just the subsets of {4, 5, 2, 1}, tacking on a 3 at the end. Thus, you can generate the subsets, in pseudocode like this:

    Code:
    // findSubsets returns a set of sets, basically the list of subsets.
    Set findSubsets(Set A)
    {
         if A is the empty set
                return the empty set
    
         // The first element of our set is A[0]
         // (A - A[0] is the set A without the first element)
         Set B := findSubsets(A - A[0])
         
         // Set B is now all the subsets of A without the first element
         // We now find all the subsets of A containing the first element by finding
         // tacking on the first element to the sets inside B
         Set C = {}
         For each set D in B
                add {A[0], D} to C
       
        return B added to C
    }
    I'll now test it out on a few examples.
    1. The empty sets works. If A = {}, the first if statement, which checks for the base case, fires, and so the empty set is returned.
    2. Now, let's try a slightly more complicated example. Does A = {3} work? For the first iteration, B := findSubsets({}); we've already shown the empty set returns the empty set. Thus, B := {{}}. Going further, Set C is each set in B tacking on 3, the first element. The only set in B is the empty set; so, C := {{3}}. Adding the two sets together and the return is {{}, {3}}. This return is correct.

    Now that I've given a few examples, you'll probably want to try a few more, perhaps even writing code to implement the function.

  8. #8
    Registered User
    Join Date
    Oct 2005
    Posts
    14
    Hi@all

    I wrote a program according to the algorithm that okinrus mensioned it above. When I run my program, I can not see the output. I think problem is in my add function.

    Can anyone help me to fix my problem?

    thanks

    my code:
    Code:
    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    
    string function (string& str);
    string add(string  c, string sdr);
    string combine (string one, string two);
    
    int main()
    {
    	
    	string input;
    
    	cin>>input;
    
    	cout<<function(input)<<endl;
    
    	return 0;
    }
    
    string function(string& str)
    {
    
    	if (str==" ")
    	{
    		return str;
    	}
    		
    	else
    	{
    		string c;
    		c= str[0];
    	
    		str.erase(0,1);
    		
    		string temp;
    
    		temp=function(str.erase(0,1));
    		
    		return combine (add(c,temp),temp);
    
    		
    	}
    
    }
    
    string add(string  c, string sdr)
    {
    	for (int i=0; i<sdr.size(); i++)
    	
    		 sdr.insert(i,c);
    
    	return sdr;
    	
    	
    }
    
    string combine(string one, string two)
    {
    	for (int i=0; i<two.size(); i++)
    		one[one.size()]=two[i];
    	
    
    	return one;
    }
    sample input:
    ABC

    sample output: (output order can be changed)
    AB
    AC
    BC
    A
    B
    C
    Last edited by merixa; 11-09-2005 at 02:07 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C or C++
    By AcerN30 in forum Game Programming
    Replies: 41
    Last Post: 05-30-2008, 06:57 PM
  2. The new FAQ
    By Hammer in forum A Brief History of Cprogramming.com
    Replies: 34
    Last Post: 08-30-2006, 10:05 AM
  3. C help for network animator
    By fastshadow in forum Tech Board
    Replies: 7
    Last Post: 03-17-2006, 03:44 AM
  4. OpenGL Window
    By Morgul in forum Game Programming
    Replies: 1
    Last Post: 05-15-2005, 12:34 PM
  5. Find Dialog
    By Lithorien in forum Windows Programming
    Replies: 6
    Last Post: 04-25-2005, 05:28 PM