# STLAlgorithmExtensions/PowerSet

BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List

Difference (from prior major revision) (author diff)

Changed: 21,34c21
 bool next_SubSet?(SubSet?& s) { if (s._cont_iter.size() == s._L - s._F) return false; SubSet?::Iter it = s._F; if (s.cont.size() == 0 || s.cont[0] != it) s.cont.push_front(it); SubSet?::Iter it2 = it; int i = 0; while (it2++ == s.cont[i++]); s.cont.erase(0, i);//erase [it..it2) s.cont.push_front(it2); return true; }
 bool next_SubSet?(SubSet?& s);

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.

BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List