Recursively find subsets

Question

Here is the recursive function that I am trying to create that finds all the subsets passed in the STL set. the two parameters are a set of STLs for finding items, and the number i> = 0, which indicates how large the subsets should be. If the integer is greater, then the set returns an empty subset

I do not think that I am doing it right. Sometimes it's right, sometimes not. The stl set goes 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

As far as I understand, are you really trying to generate all subsets of "i" elements from a given set?

Changing the input data set will lead you into trouble; you better not change it.

I think this idea is quite simple, although I would say that you got it back. Since this looks like homework, I will not give you an algorithm in C ++;)

 generate_subsets(set, sizeOfSubsets) # I assume sizeOfSubsets cannot be negative # use a type that enforces this for god 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 

Key points are:

• generate lower-level subsets first, as you will have to iterate over them
• do not try to insert an element into a subset, if it already exists, it will give you a subset of the wrong size

Now you need to understand this and transfer it to the "real" code.

Answer 2

I looked at this for a few minutes, and I can’t understand what your train of thought is, thinking that it will work. You are constantly deleting several members of the input list before exploring all the possible subsets in which they could participate.

Try to develop a solution that you intend to use in pseudo-code, and see if you can see the problem without stl intervention.

Answer 3

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

You can find methods for calculating power on the PowerSonic Wikipedia setup page and on Math Is Fun (the link is in the External links section on which the Wikipedia page is called Power Set from Math Is Fun, and I can not publish it directly here, because the mechanism for preventing spam ) In math, it’s funny mainly the It section, binary.

Answer 4

I also do not see what this should achieve.

If this is not homework with specific limitations, I just suggest testing against a temporary std::set with std::includes() .