recursively find subsets

Question

Here is a recursive function that I'm trying to create that finds all the subsets passed in an STL set. the two params are an STL set to search for subjects, and a number i >= 0 which specifies how big the subsets should be. If the integer is bigger then the set, return empty subset

I don't think I'm doing this correctly. Sometimes it's right, sometimes its not. The stl set gets passed in fine.

list<set<int> > findSub(set<int>& inset, int i)
{
    list<set<int> > the_list;

    list<set<int> >::iterator el = the_list.begin();
    if(inset.size()>i)
    {

     set<int> tmp_set;
     for(int j(0); j<=i;j++)
     {
      set<int>::iterator first = inset.begin();
      tmp_set.insert(*(first));
      the_list.push_back(tmp_set);
      inset.erase(first);
     }

     the_list.splice(el,findSub(inset,i));
    }

    return the_list;
}

Answer 1

I have been staring at this for several minutes and I can't figure out what your train of thought is for thinking that it would work. You are permanently removing several members of the input list before exploring every possible subset that they could participate in.

Try working out the solution you intend in pseudo-code and see if you can see the problem without the stl interfering.

Answer 2

I also can't see what this is supposed to achieve.

If this isn't homework with specific restrictions i'd simply suggest testing against a temporary std::set with std::includes().

Answer 3

From what I understand you are actually trying to generate all subsets of 'i' elements from a given set right ?

Modifying the input set is going to get you into trouble, you'd be better off not modifying it.

I think that the idea is simple enough, though I would say that you got it backwards. Since it looks like homework, i won't give you a C++ algorithm ;)

generate_subsets(set, sizeOfSubsets) # I assume sizeOfSubsets cannot be negative
                                     # use a type that enforces this for god's sake!
  if sizeOfSubsets is 0 then return {}
  else if sizeOfSubsets is 1 then
    result = []
    for each element in set do result <- result + {element}
    return result
  else
    result = []
    baseSubsets = generate_subsets(set, sizeOfSubsets - 1)
    for each subset in baseSubssets
      for each element in set
        if no element in subset then result <- result + { subset + element }
    return result

The key points are:

• generate the subsets of lower rank first, as you'll have to iterate over them
• don't try to insert an element in a subset if it already is, it would give you a subset of incorrect size

Now, you'll have to understand this and transpose it to 'real' code.

Answer 4

It seems (I'm not native English) that what you could do is to compute power set (set of all subsets) and then select only subsets matching condition from it.

You can find methods how to calculate power set on Wikipedia Power set page and on Math Is Fun (link is in External links section on that Wikipedia page named Power Set from Math Is Fun and I cannot post it here directly because spam prevention mechanism). On math is fun mainly section It's binary.