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.

---

Ah, also called "kSubsets", right? I have an implementation ready... :rolleyes:

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

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.

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.

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

---

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.

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