math: combinations of i amongst n elements
Hi, Is there an available function to generate all the i-tuples among a sequence of size n (runtime) and 1<= i <=n For e.g. in a vector of 3 ints 1 2 and 3 we want to get all of the singletons: 1 2 3 all the pairs 1 2 1 3 2 3 and all the triplets 1 2 3 If not and I were to write one (n known at runtime only), what signature should I use? template <typename iterator> .... combinations(iterator begin, iterator end) { } what return type would hold all of the singletons, pairs, triplets, ... n-tuples Perhaps a better signature is template <typename iterator> .... combinations(iterator begin, iterator end, int i) { } but then the return type is still not easy to define. I'm thinking a 2D multi_array where not all the space is used (dim1 size is 2^n and dim2 size is n), and pass it by ref template <typename iterator> void combinations(multi_array& out, iterator begin, iterator end) { } regards,
I suggest creating a class which contains a boost::multi_array with
dimensions nCi, i.
Alternatively (or in addition), create a class with a std::vector of length
i and with a next() method and compute the combinations as you need them.
The only tricky part of this is that you need to know the datatype that the
template type iterator dereferences too. In c++0x you can do
"decltype(*iterator())" or "decltype(*begin)" or something of that effect,
but in plain c++, I'm not sure you can do any better than just passing the
datatype in as a template parameter.
e.g. in plain c++
template
template <typename Iterator> inline bool next_combination(const Iterator first, Iterator k, const Iterator last) { /* Credits: Thomas Draper */ if ((first == last) || (first == k) || (last == k)) return false; Iterator itr1 = first; Iterator itr2 = last; ++itr1; if (last == itr1) return false; itr1 = last; --itr1; itr1 = k; --itr2; while (first != itr1) { if (*--itr1 < *itr2) { Iterator j = k; while (!(*itr1 < *j)) ++j; std::iter_swap(itr1,j); ++itr1; ++j; itr2 = k; std::rotate(itr1,j,last); while (last != j) { ++j; ++itr2; } std::rotate(k,itr2,last); return true; } } std::rotate(first,k,last); return false; }
participants (3)
-
Arash Partow -
Clinton Mead -
Hicham Mouline