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 setsWhile 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_iteratorPre-condition:

[_F2 _L2) is sortedReturns:

true iff next after 2 in lexicographical order subset of 1 existsPost-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