STLAlgorithmExtensions/PowerSet

power set algorithm

Hmm, what kind of interface would you suggest here?

I think it should be like std::next_permutation, or even [SuperSets iterator]? Maybe like that

template<class Iter, class ContIter = std::vector<Iter> >//maybe std::set
class SubSet
{
public:
   SubSet(Iter F, iter L);//empty superset of container [F..L)
   SubSet(list<Iter>);//superset from set of iterators
//there is some ambiguity so, maybe it must be make_superset, 
//make_superset_from_iterators, make superset_from_sorted_iterators
   bool contains_iter(Iter x);
//bool contains(typename Iter::value_type x); //don't know if set was sorted, maybe require that?
   ContIter::const_iterator begin() const;//allow iterating
   ContIter::const_iterator end() const;//allow iterating
};
bool next_SubSet(SubSet& s);
//of course there must be something like SubSet, based on bitset,
//as a separate class or as specialization for small sets

While writing I got idea: we need SubSet? class, not SuperSet? :) However interface is still very blurry :)

Or like that bool next_subset(_F1, _L1, _F2&, _L2&);

 Where [F1, L1) - Set
 [F2, L2) - SubSet?, i.e. container of Set::const_iterator
 F2 must be insert_iterator

Pre-condition:

 [_F2 _L2) is sorted

Returns:

 true iff next after 2 in lexicographical order subset of 1 exists

Post-condition:

 if result==true [F2 L2) is next subset, else F2==L2

But still i don't think it very usefull, it's always easier to use bit-mask to represent subset, and iterate from 0 to 2^size - 1 to get all subsets.

Disclaimer: This site not officially maintained by Boost Developers