Enumerating specific subsets using STL

Question

Say I have a series of numbers, for example {2,3,4,5}, stored in that order in std::vector v , and that I want to list all possible subsets that end in 5 using STL ... then there is:

 2 3 4 5 2 3 5 2 4 5 3 4 5 2 5 3 5 4 5 5 

(I hope I do not forget :))

I tried using while(next_permutation(v.begin(),v.end())) , but did not find the desired result :)

Does anyone have any ideas?

PS: those who made jame 2010 archives for Google can admit it :)

Answer 1

tomasz describes a solution that will work as long as n<=32 , although it will take a very long time to print 2 ^ 32 different subsets. Since the estimates for a large dataset are 2 <= n <= 500, generating all subsets is definitely not a way. You need to come up with some smart way to avoid having to generate them. In fact, this is the whole point of the problem.

You can probably find solutions by searching for this issue. My hint is that you need to look at the structure of the sets and not generate them at all. You only need to calculate how many there are.

Answer 2

Let's focus on the print problem of all subsets. As you know, if you have a vector of elements n , you will have 2^n possible subsets. It is no coincidence that if you have an n bit integer, the maximum stored value is 2^n . If you consider each integer as a vector of bits, then repeating all possible values ​​will give all possible subsets of bits. Well, we have subsets for free, iterating an integer!

Assuming that the vector contains no more than 32 elements (more than 4 billion possible subsets!), This code fragment will print all subsets of the vector v (except for the empty one):

 for (uint32_t mask =1; mask < (1<<v.size()); ++mask) { std::vector<int>::const_iterator it = v.begin(); for (uint32_t m =mask; m; (m>>=1), ++it) { if (m&1) std::cout << *it << " "; } std::cout << std::endl; } 

I simply create all possible bit masks for the size of the vector and repeat each bit; if it is installed, I print the corresponding item.

Now applying the ending rule with some specific number is a piece of cake (by checking the additional state when passing through masks). Preferably, if your vector has only one 5 character, you can swap it to the end and print all subsets of the vector without the last element.

I use std::vector , const_iterator and std::cout effectively, so you can think of it as a solution using STL. If I come up with something more STLish, I'll let you know (well, but how, it just repeats itself). You can use this function as a guideline for your STL solutions, but :-)

EDIT: As Jorgen Fogh noted, he does not solve your blues subtype if you want to work with large vectors. In fact, if you want to print all subsets for 32 elements, it will generate terabytes of data. You can use a 64-bit integer if you think that it is limited to a constant 32, but you would not even finish the iteration over all numbers. If your problem just answers how many desired subsets, you definitely need a different approach. And STL will also not be very useful; -)

Answer 3

As you can use any container, I would use std :: set, because it is close to what we want to represent. Now your task is to find all the subsets ending in 5, so that we take our initial set and remove 5 from it. Now we want all the subsets of this new set and add 5 to them at the end.

 void subsets(std::set<std::set<int>> &sets, std::set<int> initial) { if(initial.empty()) return; sets.insert(initial);//save the current set in the set of sets std::set<int>::iterator i = initial.begin(); for(; i != initial.end(); i++)//for each item in the set { std::set<int> new_set(initial);//copy the set new_set.erase(new_set.find(*i));//remove the current item subsets(sets, new_set);//recursion ... } } 

sets is a collection containing all the subsets you want. initial is the set in which you want to have subsets. Finally call it with subsets(all_subsets, initial_list_without_5);

This should create subsets, and finally you can add 5 to all of them. Btw does not forget the empty string :)

Also note that creating and deleting all of these sets is not very efficient. If you want faster, the final set should get pointers to the sets, and new_set should be dynamically allocated ...

Answer 4

use permutation to create vector vectors. Then use std :: partition with a function to sort into vectors ending in 5, and those that don't.